class Graph(object):
    """
    以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)創(chuàng)建有向網(wǎng)
    """
    def __init__(self, kind):
        # 圖的類型: 無(wú)向圖, 有向圖, 無(wú)向網(wǎng), 有向網(wǎng)
        # kind: Undigraph, Digraph, Undinetwork, Dinetwork,
        self.kind = kind
        # 頂點(diǎn)表
        self.vertexs = []
        # 邊表, 即鄰接矩陣, 是個(gè)二維的
        self.arcs = []
        # 當(dāng)前頂點(diǎn)數(shù)
        self.vexnum = 0
        # 當(dāng)前邊(弧)數(shù)
        self.arcnum = 0

    def CreateGraph(self, vertex_list, edge_list):
        """
        創(chuàng)建圖
        :param vertex_list: 頂點(diǎn)列表
        :param edge_list: 邊列表
        :return:
        """
        self.vexnum = len(vertex_list)
        self.arcnum = len(edge_list)
        for vertex in vertex_list:
            vertex = Vertex(vertex)
            # 頂點(diǎn)列表
            self.vertexs.append(vertex)
            # 鄰接矩陣, 初始化為無(wú)窮
            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):
        """
        定位頂點(diǎn)在鄰接表中的位置
        :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):
        """
        創(chuàng)建鄰接矩陣
        :param ivertex:
        :param jvertex:
        :param weight:
        :return:
        """
        if self.kind == 'Dinetwork':
            self.arcs[ivertex][jvertex] = weight

 def Dijkstra(self, Vertex):
        """
        Dijkstra算法, 計(jì)算源點(diǎn)Vertex到其余各頂點(diǎn)的最短距離
        :param Vertex:
        :return:
        """
        # 源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長(zhǎng)度
        Dist = []
        # 每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)(弧尾下標(biāo))
        Path = []
        # 記錄頂點(diǎn)是否已求得最短路徑
        flag = [False] * self.vexnum

        index = 0
        while index < self.vexnum:
            Dist.append(self.arcs[Vertex][index])
            if self.arcs[Vertex][index] < float('inf'):
                # 存放弧尾下標(biāo)
                Path.append(Vertex)
            else:
                Path.append(-1)
            index += 1

        # 以頂點(diǎn)Vertex為源點(diǎn)
        Dist[Vertex] = 0
        Path[Vertex] = 0
        flag[Vertex] = True

        index = 1
        while index < self.vexnum:
            minDist = float('inf')
            # 尋找源點(diǎn)到下一個(gè)頂點(diǎn)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')
            # 更新源點(diǎn)到終點(diǎn)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):
        """
        輸出從頂點(diǎn)Vertex到其余頂點(diǎn)的最短路徑
        :param Vertex:
        :param Dist:
        :param Path:
        :return:
        """
        tPath = []
        index = 0
        while index < self.vexnum:
            # index是路徑終點(diǎn)
            if index != Vertex:
                print('頂點(diǎn)' + self.vertexs[Vertex].data + '到達(dá)頂點(diǎn)' + self.vertexs[index].data + '的路徑及長(zhǎng)度為:')
                # 從源點(diǎn)Vertex到終點(diǎn)index中間有可能經(jīng)過(guò)了多個(gè)頂點(diǎn)
                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

 def Floyd(self):
        """
        Floyd算法, 計(jì)算每一對(duì)頂點(diǎn)間的最短距離
        :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
        
        # 判斷圖中任意兩個(gè)頂點(diǎn)的最短路徑是否經(jīng)過(guò)了結(jié)點(diǎn)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]
        # 輸出每一組頂點(diǎn)間的最短路徑
        self.ShortestPathFloyd(Dist, Path)

    def ShortestPathFloyd(self, Dist, Path):
        """
        輸出每一組頂點(diǎn)間的最短路徑
        :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('從頂點(diǎn)' + self.vertexs[start].data + '到頂點(diǎn)' + self.vertexs[end].data +
                          '的路徑及長(zhǎng)度為:')
                    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()