最短路
输入“/”快速插入内容
最短路
最短路
飞书用户16578月12日修改
在现实生活中，很多问题都可以转化为图来解决。例如，计算地图中两地之间的最短路径、网络最小成本布线，以及工程进度控制等等。
Dijkstra算法
给定有向带权图 G =( V ,Ｅ )，其中每条边的权值都是非负实数。 此外，给定 V 中的一个节点，称之为源点。求解从源点到其他各个节点的最短路径长度，路径长度指路上各边权之和。
⚽
如何求源点到其他各个节点的最短路径长度呢？
荷兰计算机科学家迪科斯彻提出了著名的单源最短路径求解算法 ——Dijkstra算法。Dijkstra算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个节点的最短路径。
Dijkstra算法的基本思想：
假定源点是u，节点集合V 被划分为两部分：集合S和集合V−S。在集合S中的节点到源点的最短路径已经确定。集合 V−S 所包含的节点到源点的最短路径的长度待定，称从源点出发只经过集合 S 中的节点到达集合 V−S中的节点的路径为特殊路径，并用数组dist[]记录当前每个节点所对应的最短特殊路径长度。pre[i]记录最短路径上节点i的前驱,找具体的路径。
Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径， 将其连接的集合V−S中的节点加入集合 S 中，同时更新数组dist[]。一旦集合S包含所有节点，dist[]就是从源点到所有其他节点的最短路径长度。
图解：
假设图的信息如下：
1、初始化如下，过程如以下动图所示：
2、确定源点，假设源点是1，将dis[源点] = 0
🌅
对于一条从点u到点v，权值为w的边
dis[u] : 此刻从源点到u最短距离
dis[v]: 此刻从源点到v最短距离
如果dis[u] + w < dis[v] , 说明v这个点可以借助u这个点， v --> u --> 源点，缩短到源点的距离
这代表这这条边是之前没有被发现的，且比原来还短，将dis[v] = dis[u] + w,这种操作称为松弛
3、找最小。在集合V−S={1,2,3,4,5}中查找dist[]最小的节点 t ，找到的最小值为0，对应的节点 t = 1，最小的点放到s中，同时更新集合为V−S={2,3,4,5}，并看集合V−S中点借助节点t能否更新dis[]的值，过程如以下动图所示。
🏝️
dis[2]此时为∞：
•
1 --> 2 有边， 权值w为2
•
dis[1] 是 0, dis[1] + edge[1][2] < dis[2], 此时更行dis[2] = dis[1] + edge[1][2] = 2
•
记录 pre[2] = 1, 目前点2前面的点是1