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最短路徑內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: