import networkx as nx
import matplotlib.pyplot as plt
import numpy as np


class Distance():
    def __init__(self,matrix):
        self.matrix = matrix

    def Dijkstras(self,start_vertex):
        length=len(self.matrix)
        # 已经访问过的顶点
        visited_vertex = [start_vertex]
        #用于记录路径中的节点的父节点
        path_parent = [start_vertex]*length
        real_distance = []
        temp_distance = []
        real_distance.extend(self.matrix[start_vertex])
        temp_distance.extend(self.matrix[start_vertex])
        temp_distance[start_vertex]=10**10
        #真实路径
        real_path = []
        while(len(visited_vertex)<length):
            #子路径
            subpath =[]
            num= temp_distance.index(min(temp_distance))#找出该路径中最小权重对应的顶点
            temp_distance[num]=100**100 #用10**10表示无穷大
            subpath.append(str(num))#
            i=num
            while(path_parent[i]!=start_vertex):#回溯，直到父节点是start_vertex
                subpath.append(str(path_parent[i]))#
                i=path_parent[i]
            subpath.append(str(start_vertex))#
            subpath.reverse()
            visited_vertex.append(num)
            real_path.append(subpath)
            for k in range(length):
                if k not in visited_vertex:
                    if (self.matrix[num][k]+real_distance[num])<real_distance[k]:
                        real_distance[k]=self.matrix[num][k]+real_distance[num]
                        temp_distance[k]=self.matrix[num][k] + real_distance[num]
                        path_parent[k]=num
        return real_path,real_distance

def graphplot(matrix,distance):
    G =nx.Graph() #创建空网络图
    for i in range(len(matrix)):
        for j in range(len(matrix[i])-1):
            # G.add_edge(matrix[i][j],matrix[i][j+1])
            G.add_edge(matrix[i][j],matrix[i][j+1],weight=distance[matrix[i][j]][matrix[i][j+1]])
    #节点位置
    pos = nx.spring_layout(G)  # positions for all nodes
    # 首先画出节点位置
    # # nodes
    nx.draw_networkx_nodes(G, pos, node_size=900)
    # 根据权重，实线为权值大的边，虚线为权值小的边
    # edges
    nx.draw_networkx_edges(G, pos)
    # labels标签定义
    edge_labels = nx.get_edge_attributes(G, 'weight')
    labels = {0: '南京', 1: '无锡', 2: '徐州', 3: '常州',
              4: '苏州', 5: '南通', 6: '连云港', 7: '淮安',
              8: '盐城', 9: '扬州', 10: '镇江', 11: '泰州',
              12: '宿迁'}
    nx.draw_networkx_edge_labels(G, pos,edge_labels, font_family='sans-serif')
    nx.draw_networkx_labels(G, pos, labels,font_size=10, font_family='sans-serif')
    #nx.draw_networkx_labels(G, pos, font_family='sans-serif'

    # 解决中文显示问题
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.rcParams['axes.unicode_minus'] = False

    plt.title('江苏省最优高铁设计图（Dijkstras）', fontsize='xx-large')
    plt.axis('on')
    plt.xticks([])
    plt.yticks([])
    plt.show()
    
def matrix_for_plot(matrix):#为调整下标，将字符转换成数字
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            matrix[i][j]=int(matrix[i][j])#+1
    return matrix

if __name__ == '__main__':
    inf = 100** 100  # 代替表示无穷大
    
    distance = [[0, inf, inf, 133, inf, inf, inf, inf, inf, 100, 75, inf, inf],
        [inf, 0, inf, 47, 46, inf, inf, inf, inf, inf, inf, inf, inf], 
        [inf, inf, 0, inf, inf, inf, 202, inf, inf, inf, inf, inf, 120], 
        [133, 47, inf, 0, inf, inf, inf, inf, inf, inf, 74, inf, inf], 
        [inf, 46, inf, inf, 0, inf, inf, inf, inf, inf, inf, inf, inf], 
        [inf, inf, inf, inf, inf, 0, inf, inf, 177, inf, inf, 124, inf],
        [inf, inf, 202, inf, inf, inf, 0, 158, 253, inf, inf, inf, 145],
        [inf, inf, inf, inf, inf, inf, 158, 0, 127, inf, inf, inf, 100],
        [inf, inf, inf, inf, inf, 177, 253, 127, 0, inf, inf, 138, inf],
        [100, inf, inf, inf, inf, inf, inf, inf, inf, 0, 100, 62, inf], 
        [75, inf, inf, 74, inf, inf, inf, inf, inf, 100, 0, inf, inf], 
        [inf, inf, inf, inf, inf, 124, inf, inf, 138, 62, inf, 0, inf],
        [inf, inf, 120, inf, inf, inf, 145, 100, inf, inf, inf, inf, 0]]

    chararray = ['南京','无锡','徐州','常州',
                '苏州','南通','连云港','淮安',
                '盐城','扬州','镇江','泰州','宿迁']
    L=[]
    for i in range(0,len(chararray)):
        L.append('%d'%i)
    Dict=dict(zip(L,chararray))
    print('城市与编号之间的对应关系：')
    print(Dict)
    print('-------------------------------------------------------------')

    test = Distance(distance)
    wholeroute=[]
    for i in range(len(distance)):
        route,vertex_distance=test.Dijkstras(i)#存放的是字符，如‘1’，‘5’
        wholeroute.extend(route)
        print('编号{}的城市通往其他城市的最短路径：'.format(route[0][0]))
        for j in range(len(route)):
            # for k in range(len(route[j])):
            print("->".join(route[j]),'两城市间最短总路径为：{}'.format(vertex_distance[int(route[j][-1])]))#最后输出时，所有总距离都取整数
            #for k in range(len(route[j]))
    graphplot(matrix_for_plot(wholeroute),distance)