首页 > 代码库 > Dijkstra(单源最短路算法)
Dijkstra(单源最短路算法)
typedef struct graph{
int val;
int weight;
}graph;
graph g[1005][1005],dist[1005];
int visit[1005];
void dijkstra(int start,int n)
{
int min,u;
for(int i=1;i<=n;i++)
{
dist[i].val = MAXVAL;
visit[i]=0;
}
for(int i=1;i<=n;i++)
{
if(g[start][i].val < MAXVAL)
{
dist[i].val = g[start][i].val;
dist[i].weight = g[start][i].weight;
}
}
visit[start] = 1;
dist[start].val = 0;
for(int i=1;i<=n;i++)
{
min = MAXVAL;
u = 0;
for(int k=1;k<=n;k++) //找出每一轮最短路径的顶点
{
if(visit[k]==0 && dist[k].val < min)
{
min = dist[k].val;
u = k;
}
}
visit[u] = 1;
for(int j=1;j<=n;j++) //更新最短路径
{
if(visit[j]==0 && dist[j].val > (dist[u].val + g[u][j].val))
{
dist[j].val = dist[u].val + g[u][j].val;
dist[j].weight = dist[u].weight + g[u][j].weight;
}
else if(visit[j]==0 && dist[j].val == (dist[u].val + g[u][j].val))
{
if(dist[j].weight > (dist[u].weight + g[u][j].weight))
{
dist[j].weight = dist[u].weight + g[u][j].weight;
}
}
}
}
}
Dijkstra(单源最短路算法)