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)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。