python实现Dijkstra算法的最短路径问题
119 浏览量
2020-09-19
06:34:25
上传
评论 3
收藏 81KB PDF 举报
python实现实现Dijkstra算法的最短路径问题算法的最短路径问题
主要介绍了python实现Dijkstra算法的最短路径问题，文中通过示例代码介绍的非常详细，对大家的学习或者工
作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
迪杰斯特拉（Dijkstra）算法主要是针对没有负值的有向图，求解其中的单一起点到其他顶点的最短路径算法。
1 算法原理算法原理
迪杰斯特拉（Dijkstra）算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有向图，作为程序中的实
验数据。
其中，带权值的有向图采用邻接矩阵graph来进行存储，在计算中就是采用n*n的二维数组来进行存储，v0-v5表示数组的索引
编号0-5，二维数组的值表示节点之间的权值，若两个节点不能通行，比如，v0->v1不能通行，那么graph[0,1]=+∞ （采用计
算机中最大正整数来进行表示）。那如何求解从v0每个v节点的最短路径长度呢?
首先，引进一个辅助数组cost，它的每个值cost[i]表示当前所找到的从起始点v0到终点vi的最短路径的权值（长度花费），该
数组的初态为：若从v0到vi有弧，则cost[i]为弧上的权值，否则置cost[i]为+∞。
显然，长度为：cost[j]=Min_i(graph[0,i] | v_i in V)
的路径就是从
v0
出发的长度最短的一条最短路径。此路径为
(v_0,v_j)
，那么
下次长度次短的路径必定是弧
(v_0,v_i)
上的权值
cost[i](v_i in V)
，或者是
cost[k](v_k in S)
和弧
(v_k,v_i)
的权值之和。其中
V
：待
求解最短路径的节点
j
集合；
S
：已求解最短路径的节点集合。
2 算法流程算法流程
根据上面的算法原理分析，下面描述算法的实现流程。
初始化：初始化辅助数组cost，从v0出发到图上其余节点v的初始权值为：cost[i]=graph[0,i] | v_i in V ；初始化待求节点S集
合，它的初始状态为始点，V集合，全部节点-始节点。
选择节点v_j ，使得cost[j]=Min ( cost[i] | v_i in V -S ) ，v_j 就是当前求的一条从v0出发的最短路径的终点，修改S集合，使得
S=S + V_j ，修改集合V = V - V_j。
修改从v0出发到节点V-S上任一顶点 v_k 可达的最短路径，若cost[j]+graph[j,k]<cost[k] ，则修改cost[k]为：
cost[k]=cost[j]+graph[j,k] 。
重复操作2，3步骤，直到求解集合V中的所有节点为止。
其中最短路径的存储采用一个path整数数组，path[i]的值记录vi的前一个节点的索引，通过path一直追溯到起点，就可以找到
从vi到起始节点的最短路径。比如起始节点索引为0，若path[3]=4, path[4]=0；那么节点v2的最短路径为，v0->v4->v3。
评论0