Dijkstra算法
2020-12-13 14:18
标签：直接 book png code 指定 ret 其他 执行 标记 迪杰斯特拉（Dijkstra）是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展（广度优先搜索的思想），直到扩展到终点为止。 （第一段是抄的，由于本人是个算法小白。官方的话还是抄的好） 有这么一个加权图，Dijkstra算法可以计算任意节点到其他节点的最短路径。 算法思路： 1.指定一个节点，例如我们要计算‘A’到其他节点的最短路径 2.定义两个集合（S,U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径长度，上图A->C没有直接路径，初始化为inf（inf==0x7fffffff））； 3.初始化两个集合，S初始化时只有当前要计算的节点，A->A = 0；U集合初始化为A->B = 4,A->D = 2,A->C = inf,A->E = inf; 4.从U集合中找出路径最短的点，加入S集合，A->D=2； 5.更新U集合路径，if（‘D‘到‘B‘,‘C‘,‘E‘的距离+‘AD的距离’ 6.循环执行4、5，直到遍历结束，得到A到其他节点的最短路径。 下面贴上一段图解（借鉴的别人的0.0） Dijkstra算法 标签：直接 book png code 指定 ret 其他 执行 标记 原文地址：https://www.cnblogs.com/speedsnail/p/11558747.html
int Dijkstra(int x, int y) {//点x到点y的距离
int i, j;
int book[210];//加入了集合S的点做标记
memset(book, 0, sizeof(book));
int dis[210];//集合U
memset(dis, 0, sizeof(dis));
for (i = 0; i ) {
dis[i] = G[x][i];//先初始化点x到其他的点的距离
}
book[x] = 1;
for (i = 0; i ) {
int min1 = inf, k = x;
for (j = 0; j ) {
if (!book[j] && dis[j] min1) {//找到集合U中路径最短的点
min1 = dis[j];
k = j;
}
}
book[k] = 1;
for (j = 0; j ) {
if (!book[j] && dis[j] > min1 + G[k][j]) {//更新
dis[j] = min1 + G[k][j];
}
}
}
return dis[y];
}
下一篇：C# volatile与lock