这篇教程Python实现最短路径问题的方法写得很实用，希望能帮到您。
一、创建图在开始之前，我们先创建一个图，使用邻接矩阵表示有向网： class Graph(object): """ 以邻接矩阵为存储结构创建有向网 """ def __init__(self, kind): # 图的类型: 无向图, 有向图, 无向网, 有向网 # kind: Undigraph, Digraph, Undinetwork, Dinetwork, self.kind = kind # 顶点表 self.vertexs = [] # 边表, 即邻接矩阵, 是个二维的 self.arcs = [] # 当前顶点数 self.vexnum = 0 # 当前边(弧)数 self.arcnum = 0 def CreateGraph(self, vertex_list, edge_list): """ 创建图 :param vertex_list: 顶点列表 :param edge_list: 边列表 :return: """ self.vexnum = len(vertex_list) self.arcnum = len(edge_list) for vertex in vertex_list: vertex = Vertex(vertex) # 顶点列表 self.vertexs.append(vertex) # 邻接矩阵, 初始化为无穷 self.arcs.append([float('inf')] * self.vexnum) for edge in edge_list: ivertex = self.LocateVertex(edge[0]) jvertex = self.LocateVertex(edge[1]) weight = edge[2] self.InsertArc(ivertex, jvertex, weight) def LocateVertex(self, vertex): """ 定位顶点在邻接表中的位置 :param vertex: :return: """ index = 0 while index < self.vexnum: if self.vertexs[index].data == vertex: return index else: index += 1 def InsertArc(self, ivertex, jvertex, weight): """ 创建邻接矩阵 :param ivertex: :param jvertex: :param weight: :return: """ if self.kind == 'Dinetwork': self.arcs[ivertex][jvertex] = weight 有关邻接矩阵中顶点结点Vertex()的定义可以参考这篇博客，这里就不在贴出相应的代码了。
二、问题来源
假如我从城市 A A A出发坐火车去其他城市旅游，那么如何规划路线使所花费的车票钱最少呢？若将上述图中的城市看成有向网中的顶点，并将两城市之间所需要的车票钱看做对应弧的权值，那么这一问题的本质就是求两个顶点之间权值最小的路径，简称最短路径 ( S h o r t e s t (Shortest (Shortest P a t h ) Path) Path)。
三、Dijkstra算法D i j k s t r a Dijkstra Dijkstra算法，中文名叫迪杰斯特拉算法，它常用于求解源点到其余顶点的最短路径。 假设 G = { V , { A } } G=/{V, /{A/}/} G={V,{A}}是含有 n n n个顶点的有向网，以该图中的顶点 v v v为源点，使用 D i j k s t r a Dijkstra Dijkstra算法求顶点 v v v到图中其余各顶点的最短路径的基本思路如下：
(1) 使用集合 S S S记录已求得最短路径的终点，初始时 S = { v } S=/{v/} S={v}；
(2) 选择一条长度最短的路径，该路径的终点 w ∈ V − S w/in V-S w∈V−S，将 w w w并入 S S S，并将该最短路径的长度记为 D w D_w Dw；
(3) 对于 V − S V-S V−S中任一顶点 s s s，将源点到顶点 s s s的最短路径长度记为 D s D_s Ds，并将顶点 w w w到顶点 s s s的弧的权值记为 D w s D_{ws} Dws，若 D w + D w s < D s D_w+D_{ws}<D_s Dw+Dws<Ds，则将源点到顶点 s s s的最短路径的长度修改为 D w + D w s D_w+D_{ws} Dw+Dws；
(4) 重复执行上述操作，直到 S = V S=V S=V。 D i j k s t r a Dijkstra Dijkstra算法有些 P r i m Prim Prim算法的影子，这里使用一个辅助列表Dist，用来存储源点到每一个终点的最短路径长度，列表Path来存储每一条最短路径中倒数第二个顶点的下标(弧尾下标)，除此之外还需要一个列表flag来记录顶点是否已求得最短路径。下面结合着 D i j k s t r a Dijkstra Dijkstra算法来分析一下上面的那个有向网： 
(1) 这里要做的就是更新列表Dist和列表Path，假如以顶点 A A A为起始点，先将它加入 S S S中，然后寻找以顶点 A A A为弧尾的最短路径，这里找到了顶点 B B B，然后继续找下一个顶点。这个时候就要做一个判断了，即 D w + D w s < D s D_w+D_{ws}<D_s Dw+Dws<Ds是否成立，这里的顶点 s s s有两种选择，要么是顶点 C C C，要么是顶点 D D D，因为这两个顶点都是以顶点 w w w(即顶点 B B B)为弧尾，按照顺序，这个时候先选择了顶点 C C C，经判断： D A B + D B C < D A C D_{AB}+D_{BC}<D_{AC} DAB+DBC<DAC(即 4 + 3 = 7 < 8 4+3=7<8 4+3=7<8)成立，然后更新源点到顶点 s s s(即顶点 C C C)的距离为7。这个时候顶点 s s s又选择了顶点 D D D，经判断： D A B + D B D < D A D D_{AB}+D_{BD}<D_{AD} DAB+DBD<DAD(即 4 + 8 = 12 < ∞ 4+8=12</infty 4+8=12<∞)成立，然后更新源点到顶点 s s s(即顶点 D D D)的距离为12。 (2) 然后寻找以顶点 C C C为弧尾的最短路径，这里找到了顶点 E E E，然后做一个路径长度判断，经判断： D A C + D C E < D A E D_{AC}+D_{CE}<D_{AE} DAC+DCE<DAE(即 7 + 1 = 8 < ∞ 7+1=8</infty 7+1=8<∞)成立，然后更新源点到顶点 s s s(即顶点 E E E)的距离为8，然后又找到了顶点 F F F，然后做一个路径长度判断，经判断： D A C + D C F < D A F D_{AC}+D_{CF}<D_{AF} DAC+DCF<DAF(即 7 + 6 = 13 < ∞ 7+6=13</infty 7+6=13<∞)成立，然后更新源点到顶点 s s s(即顶点 F F F)的距离为13。 (3) 直至计算出所有源点到其余顶点的距离。 D i j k s t r a Dijkstra Dijkstra算法代码实现如下： def Dijkstra(self, Vertex): """ Dijkstra算法, 计算源点Vertex到其余各顶点的最短距离 :param Vertex: :return: """ # 源点到每一个终点的最短路径长度 Dist = [] # 每一条最短路径中倒数第二个顶点的下标(弧尾下标) Path = [] # 记录顶点是否已求得最短路径 flag = [False] * self.vexnum index = 0 while index < self.vexnum: Dist.append(self.arcs[Vertex][index]) if self.arcs[Vertex][index] < float('inf'): # 存放弧尾下标 Path.append(Vertex) else: Path.append(-1) index += 1 # 以顶点Vertex为源点 Dist[Vertex] = 0 Path[Vertex] = 0 flag[Vertex] = True index = 1 while index < self.vexnum: minDist = float('inf') # 寻找源点到下一个顶点wVertex的最短路径 for i in range(self.vexnum): if not flag[i] and Dist[i] < minDist: wVertex = i minDist = Dist[i] flag[wVertex] = True sVertex = 0 minDist = float('inf') # 更新源点到终点sVertex的最短路径 while sVertex < self.vexnum: if not flag[sVertex]: if self.arcs[wVertex][sVertex] < minDist and / Dist[wVertex] + self.arcs[wVertex][sVertex] < Dist[sVertex]: # 距离更新 Dist[sVertex] = Dist[wVertex] + self.arcs[wVertex][sVertex] Path[sVertex] = wVertex sVertex += 1 index += 1 # 输出信息 self.ShortestPathDijkstra(Vertex, Dist, Path) def ShortestPathDijkstra(self, Vertex, Dist, Path): """ 输出从顶点Vertex到其余顶点的最短路径 :param Vertex: :param Dist: :param Path: :return: """ tPath = [] index = 0 while index < self.vexnum: # index是路径终点 if index != Vertex: print('顶点' + self.vertexs[Vertex].data + '到达顶点' + self.vertexs[index].data + '的路径及长度为:') # 从源点Vertex到终点index中间有可能经过了多个顶点 tPath.append(index) former = Path[index] while former != Vertex: tPath.append(former) former = Path[former] tPath.append(Vertex) while len(tPath) > 0: print(self.vertexs[tPath.pop()].data, end='') print('/t/t%d' % Dist[index]) index += 1
四、Floyd算法F l o y d Floyd Floyd算法，中文名叫弗洛伊德算法，它常用于求解求解每一对顶点之间的最短路径。 假设 G = { V , { A } } G=/{V, /{A/}/} G={V,{A}}是含有 n n n个顶点的有向网，使用 F l o y d Floyd Floyd算法求图中每一对顶点间的最短路径的基本思路如下： (1) 对于图 G G G中任意两个顶点 v v v和 w w w，将顶点 v v v和顶点 w w w的最短路径的长度记为 D v w D_{vw} Dvw，并依次判断其余各顶点是否为这两个顶点间最短路径上的顶点。对于除了顶点 v v v和顶点顶点 w w w的任意顶点 u u u，将顶点 v v v和顶点 u u u的最短路径的长度记为 D v u D_{vu} Dvu，并顶点 u u u和顶点 w w w的最短路径的长度记为 D u w D_{uw} Duw，若 D v u + D u w < D v w D_{vu}+D_{uw}<D_{vw} Dvu+Duw<Dvw，则将 D v w D_{vw} Dvw的值修改为 D v u + D u w D_{vu}+D_{uw} Dvu+Duw，即顶点 v v v和顶点 w w w的最短路径经过顶点 u u u； (2) 重复上述过程，直至图中每一顶点间的最短路径都被求出。 当然了，也可以对每个顶点使用 D i j k s t r a Dijkstra Dijkstra算法来求得每对顶点的最短路径。对于 F l o y d Floyd Floyd算法，这里使用一个辅助二维数组Dist，用来存储源点到每一对顶点间的最短路径长度，二维数组Path来存储每一条最短路径中倒数第二个顶点的下标(弧尾下标)。下面结合着 F l o y d Floyd Floyd算法来分析一下最上面的那个有向网（由于顶点对较多，这里选择 A − I A-I A−I的最短路径进行说明）： F l o y d Floyd Floyd算法代码实现如下： def Floyd(self): """ Floyd算法, 计算每一对顶点间的最短距离 :return: """ Dist = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)] Path = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)] for row in range(self.vexnum): for column in range(self.vexnum): Dist[row][column] = self.arcs[row][column] if self.arcs[row][column] < float('inf') and row != column: Path[row][column] = row else: Path[row][column] = -1 # 判断图中任意两个顶点的最短路径是否经过了结点uVertex for uVertex in range(self.vexnum): for vVertex in range(self.vexnum): for wVertex in range(self.vexnum): if vVertex != wVertex and / Dist[vVertex][uVertex] + Dist[uVertex][wVertex] < Dist[vVertex][wVertex]: Dist[vVertex][wVertex] = Dist[vVertex][uVertex] + Dist[uVertex][wVertex] Path[vVertex][wVertex] = Path[uVertex][wVertex] # 输出每一组顶点间的最短路径 self.ShortestPathFloyd(Dist, Path) def ShortestPathFloyd(self, Dist, Path): """ 输出每一组顶点间的最短路径 :param Dist: :param Path: :return: """ tPath = [] for start in range(self.vexnum): for end in range(self.vexnum): if start != end and Dist[start][end] < float('inf'): print('从顶点' + self.vertexs[start].data + '到顶点' + self.vertexs[end].data + '的路径及长度为:') tVertex = Path[start][end] tPath.append(end) while tVertex != -1 and tVertex != start: tPath.append(tVertex) tVertex = Path[start][tVertex] tPath.append(start) while len(tPath) > 0: print(self.vertexs[tPath.pop()].data, end='') print('/t/t%d' % Dist[start][end])
五、代码测试测试代码如下： if __name__ == '__main__': graph = Graph(kind='Dinetwork') graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'], edge_list=[('A', 'B', 4), ('A', 'C', 8), ('B', 'C', 3), ('B', 'D', 8), ('C', 'E', 1), ('C', 'F', 6), ('D', 'G', 7), ('D', 'H', 4), ('E', 'D', 2), ('E', 'F', 6), ('F', 'H', 2), ('G', 'I', 9), ('H', 'G', 14), ('H', 'I', 10)]) print('{:*^30}'.format('Dijkstra算法')) # 起始位置的index为0 graph.Dijkstra(0) print('{:*^30}'.format('Floyd算法')) graph.Floyd()测试结果如下： 
这里只看了一条，就是从顶点 A A A到顶点 I I I的路径，可以看到 D i j k s t r a Dijkstra Dijkstra算法和 F l o y d Floyd Floyd算法求得的最短路径都是24。 到此这篇关于Python实现最短路径问题的方法的文章就介绍到这了,更多相关Python最短路径内容请搜索51zixue.net以前的文章或继续浏览下面的相关文章希望大家以后多多支持51zixue.net！
用Python爬取某乎手机APP数据
Python实现单例模式的5种方法 |
