Python实现迪杰斯特拉算法过程解析
一、迪杰斯特拉算法思想
Dijkstra算法主要针对的是有向图的单元最短路径问题,且不能出现权值为负的情况!Dijkstra算法类似于贪心算法,其应用根本在于最短路径的最优子结构性质。
最短路径的最优子结构性质:
如果P(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。
证明:
假设P(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P(k,s),那么P(i,j)=P(i,k)+P(k,s)+P(s,j)
因此,Dijkstra算法描述如下:
Dijikstra算法描述如下:
假设存在G=
1)从V-S中选择使dist[i]值最小的顶点i,将i加入到U中;
2)更新与i直接相邻顶点的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}
3)直到S=V,所有顶点都包含进来了,算法停止。
二、具体操作步骤
根据其算法思想,确立操作步骤如下:
(1)初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。
(2)从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。
(3)更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4)重复步骤(2)和(3),直到遍历完所有顶点。
三、代码
defdijkstra(s,used,cost,distance,n): distance[s]=0 whileTrue: #v在这里相当于是一个哨兵,对包含起点s做统一处理! v=-1 #从未使用过的顶点中选择一个距离最小的顶点 foruinrange(n): ifnotused[u]and(v==-1ordistance[u]以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。