|
Dijkstra算法： 问题：给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。 Step: 求带权图G(V,E)的点v0到其他各点的最短路径； 1.初始时，S={v0},U={v1,v1…vn};点v0到其他点的最短距离为(i=1,2,3…n)的权；将v0到其他各点vi的最短路径中vi的前驱动点初始化为v0; 2,从U中选取u，使得当前v0到u的最短路径的距离小于v0到U中其他各点的最短路径的距离，将u加入S,并将u从U中删除 3,遍历每个在U中的点s，如果以u为中介点的最短路径的距离小于当前存储的距离，更新从v0到s的最短路径的距离，并将v0到s的最短路径的s的前驱动点更新为u; 4,重复2,3直到U为空；  绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点，dis表示源点到该顶点的最短距离
  代码：
#include
#define INF 10000000
#define MaxSize 50
int graph[MaxSize][MaxSize]; //MaxSize为最大顶点数
int dis[MaxSize]; //dis[i]为源点到顶点i的最短距离
int visit[MaxSize]; //visit[i]标记顶点i的最短路径是否已求出visit[i] == 1表示已求出
int prevetrix[MaxSize]; //前驱动点
void dij(int n)
{
int count = 0; //count是已求出最短路径的顶点数目
visit[0] = 1;
prevetrix[0] = 0;
count++;
for (int i = 1; i
int min = INF, target_index;
for (int i = 1; i
min = dis[i];
target_index = i;
}
}
visit[target_index] = 1;
count++;
for (int i = 1; i
dis[i] = dis[target_index] + graph[target_index][i];
prevetrix[i] = target_index;
}
}
}
}
int main()
{
int n, m;
scanf("%d %d", &n, &m); //n为顶点数,m为边数
int a, b, w, path[n];
for (int i = 0; i
graph[i][j] = INF;
}
}
for (int i = 0; i
if (dis[i] == INF)
{
printf("顶点0到顶点%d没有最短路径\n", i);
}
else
{
printf("顶点0到顶点%d有长为%d的最短路径：", i,dis[i]);
int cur = i, index = 0;
path[index] = cur;
while (1)
{
path[index + 1] = prevetrix[path[index]];
if (path[index + 1] == 0)
break;
index++;
}
for (int j = index + 1; j > 0; j--)
{
printf("%d->", path[j]);
}
printf("%d\n", path[0]);
}
}
}
输入：
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 5 60
4 3 20
输出：
顶点0到顶点1没有最短路径
顶点0到顶点2有长为10的最短路径：0->2
顶点0到顶点3有长为50的最短路径：0->4->3
顶点0到顶点4有长为30的最短路径：0->4
顶点0到顶点5有长为60的最短路径：0->4->3->5
注意：diskstra算法只能求边权值为非负值的情况
|