Dijkstra算法求最短路径的一个例题

邻接矩阵Dijkstra算法求最短路径

图

初始化：从源点v1出发得到矩阵 $D_0$ ，到达个点的最小路径是 $D_{12}=10$

$D_{0}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &\infty &30 &100\\ \end{array}\right ]$

第一次：从v2点出发，v1和v2保持不变，迭代剩下点(v3,v4,v5)的距离后，剩余点的最短路径是v4
$D_{1}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &60（10+50） &30 &100\\ \end{array}\right ]$

第二次：从v4出发，v1，v2,v4保持不变，优化剩余点（v3，v5）的最短距离。剩余点的最短路径是v3
$D_{2}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &50（20+30） &30 &90（30+60）\\ \end{array}\right ]$

第三次：从v3出发，v1，v2，v4，v3保持不变。优化剩余点v5的最短路径。

$D_{3}=\left[\begin{array}{cccc} v1 &v2 &v3 &v4 &v5\\ 0 &10 &50 &30 &60（20+30+10）\\ \end{array}\right ]$

源点v1的Dijkstra算法的最短路径

中间顶点	终点	路径长度
	2	10
4	3	50
	4	30
4;3	5	60

说明

在看黄杏元的GIS书籍，按照图论中用相邻矩阵来表示图是应该和书上一样全写出来的。但在寻找最短路径时候只用到了第一行向量，所以分析过程就简化了。

之后考虑会使用Python或者C++来实现一个简单图的Dijkstra算法，目前只是计划，具体什么时候写看时间吧。

Reference:

代克思托演算法 (Dijkstra's algorithm)