如何用Python详细解析实现迪杰斯特拉算法的步骤？

本文共计892个文字，预计阅读时间需要4分钟。

Dijkstra算法思想主要针对有向图的单元素最短路径问题，且不能出现权值为负的情况。该算法类似于贪心算法，其应用基本基于最短路径的最优子结构性质。

一、 迪杰斯特拉算法思想

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)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

因此，Dijkstra算法描述如下：

Dijikstra算法描述如下：

假设存在G=<V,E>，源顶点为V0，S={V0},distance[i]记录V0到i的最短距离，matrix[i][j]记录从i到j的边的权值，即两点之间的距离。

1）从V-S中选择使dist[i]值最小的顶点i，将i加入到U中；

2）更新与i直接相邻顶点的dist值。