如何用python实现最短路径？有这几种方法

有很多正在学习python的小伙伴问：如何使用python来实现最短路径呀？有什么办法没。那么本篇章我们主要来介绍介绍使用python在图的最短路径问题，包括Dijkstra算法和Floyd算法，并用Python代码实现。

用python 实现最短路径的方法具体有下面这三个方法：

（一）SPFA算法：用数组dis记录每个结点的最短路径估计值。

（二）迪杰斯特拉算法：声明一个数组dis来保存源点到各个顶点的最短距离；

（三）弗洛伊德算法：在有向图中求解点与点之间最短路径；

最短路径问题（python实现）

开发者解决最短路径问题： 

（一）SPFA算法

（二）迪杰斯特拉算法（Dijkstra算法）

（三）弗洛伊德算法（Floyd算法）

第一种算法：

SPFA这种算法是求解单源最短路径问题的一种算法，有时候我们也把SPFA算法也称为 Moore-Bellman-Ford 算法。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。

SPFA算法是优于迪科斯彻算法主要原因是因为边的权值可以为负数、实现简单，不过缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。

第二种算法：

Dijkstra算法

算法的思路

开发者声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：Q

首先，原点s的路径权重被赋为0（dis[s]=0）。如果对于顶点s存在能直接到达的边（s,m），那么就把dis[m]设为w（s, m），且同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后从dis数组中选择最小值，这个值就是源点s到该值对应的顶点的最短路径，并且把该点加入到Q中，此时完成一个顶点，再看看开发者新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值，然后，又从dis中找出最小值，重复上述动作，直到Q中包含了图的所有顶点。

第三种算法：

Floyd算法

原理：

Floyd算法（弗洛伊德算法）是一种在有向图中求最短路径的算法。它是一种求解有向图中点与点之间最短路径的算法。

用在拥有负权值的有向图中求解最短路径（不过不能包含负权回路）

流程：

有向图中的每一个节点X，对于图中过的2点A和B，

如果有Dis（AX）+ Dis（XB）< Dis（AB），那么使得Dis（AB）=Dis（AX）+Dis（XB)。

当所有的节点X遍历完后，AB的最短路径就求出来了。