当前位置 博文首页 > Python实现最短路径问题的方法

    Python实现最短路径问题的方法

    作者:夏小悠 时间:2021-08-09 17:43

    目录
    • 一、创建图
    • 二、问题来源
    • 三、Dijkstra算法
    • 四、Floyd算法
    • 五、代码测试

    一、创建图

    在开始之前,我们先创建一个图,使用邻接矩阵表示有向网:

    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。

    jsjbwy