最短路dijkstra算法详解_L3图论第04课 最短路Dijkstra算法

L3-图论-第04课 最短路Dijkstra算法

最短路

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法 和 SPFA算法等。

迪杰斯特拉(dijkstra)算法

迪杰斯特拉(dijkstra)算法是典型的用来解决最短路径的算法，由荷兰计算机科学家狄克斯特拉于1959年提出，用来求得从起始点到其他所有点最短路径。该算法采用了贪心的思想，每次都查找与该点距离最近的点，也因为这样，它不能用来解决存在负权边的图。

解决的问题大多是这样的：有一个无向图G(V,E)，边E[i]的权值为W[i]，找出V[0]到V[i]的最短路径。

算法原理

dijkstra算法基于贪心，贪心算法中最重要的一部分就是贪心策略，贪心算法对不对，就是贪心策略的正确不正确，在这个算法中，贪心策略就是，去寻找点i，满足min(d[i]) i∈B，满足这个条件的点i，必定是无法被继续松弛的点，如果说要松弛点i，那么必定通过A中或者B中的点进行更新，若通过B中的点j进行更新那么松弛之后的路径为d[j] + a[j][i] 由于d[i]已经是最小了，因此d[j]+a[j][i]>d[i] 因此不可能是通过B中的点进行松弛，若通过A中的点m进行松弛，由于m是点集A中的点，因此点m一定松弛过点i，重复的松弛没有意义的。因此，我们找到的点i，现在的d[i]，一定是从源点到点i路径最小的点了，因此，该算法的正确性是可以保证的。

实现过程

迪杰斯特拉算法流程

1. 先取一点v[0]作为起始点，初始化dis[i], dis[i]的值为v[0]到其余点v[i]的距离, 初始化为无限大, dis[0] = 0.
2. 将v[0]标记，vis[0] = 1(vis一开始初始化为0)；
3. 找寻与v[0]相邻的最近点v[k]，将v[k]点记录下来；
4. 把v[k]标记，vis[k]=1；
5. 查询并比较，让dis[j] 与 dis[k] + dis[k->j]进行比较，判断是直接v[0]连接v[j]短，还是经过v[k]连接v[j]更短，即dis[j]=MIN(dis[j],min+w[k][j])；
6. 继续重复步骤3, 4, 5，直到找出所有点为止。

示例:

1. 维护一个dis数组记录起点(按题目要求来，这里取1) 到达的所有节点的距离。(规定到自己的路径长度0，到不了的点是 inf(极大值))

2. 找出当前距离1最近的结点：4。(已经访问过的，我们标记为红色，不再次访问)