shortest_path.py

from func import *

# 无向图数据：开始计算最短路径用的rout来存储结构，后来网络分析模块必须要rout_list格式制作权值表

# 由于不想统一成rout_list,因为要改算法，就没管，路径数据保留了两份，等以后有时间了再改


rout = {'AB': 5, 'AC': 6, 'AD': 4, 'AE': 7,
             'BF': 2, 'BG': 3,'CF':6,'CG':4,'CH':1,'DG':7,'DH':3,'DI':6,'EH':9,'EI':1,
             'FJ': 2, 'FK': 3, 'GJ': 6, 'GK': 4, 'GL': 1, 'HK': 7,'HL':3,'HM':6,'IL':9,'IM':7,
             'JN': 2, 'JO': 3, 'KN': 6, 'KO': 4, 'KP': 1, 'LO': 7,'LP':10,'LQ':6,'MP':9,'MQ':8,
             'NR': 2, 'NS': 3, 'OR': 6, 'OS': 4, 'OT': 1, 'PS': 7,'PT':3,'PU':6,'QT':9,'QU':1,
             'RV': 2, 'RW': 3, 'SV': 6, 'SW': 4, 'SX': 1, 'TW': 7,'TX':3,'TY':6,'UX':9,'UY':1,
             'VZ': 5, 'WZ': 6, 'XZ': 4, 'YZ': 7
            }
rout_list = [('A', 'B', 5), ('A', 'C', 6), ('A', 'D', 4), ('A', 'E', 7),
             ('B', 'F', 2), ('B', 'G', 3), ('C', 'F', 6), ('C', 'G', 4),('C', 'H', 1), ('D', 'G', 7), ('D', 'H', 3), ('D', 'I', 6),('E', 'H', 9), ('E', 'I', 1),
             ('F', 'J', 2), ('F', 'K', 3), ('G', 'J', 6), ('G', 'K', 4), ('G', 'L', 1), ('H', 'K', 7), ('H', 'L', 3), ('H', 'M', 6), ('I', 'L', 9), ('I', 'M', 7),
             ('J', 'N', 2), ('J', 'O', 3), ('K', 'N', 6), ('K', 'O', 4), ('K', 'P', 1), ('L', 'O', 7), ('L', 'P', 10), ('L', 'Q', 6), ('M', 'P', 9), ('M', 'Q', 8),
             ('N', 'R', 2), ('N', 'S', 3), ('O', 'R', 6), ('O', 'S', 4), ('O', 'T', 1), ('P', 'S', 7), ('P', 'T', 3), ('P', 'U', 6), ('Q', 'T', 9), ('Q', 'U', 1),
             ('R', 'V', 2), ('R', 'W', 3), ('S', 'V', 6), ('S', 'W', 4), ('S', 'X', 1), ('T', 'W', 7), ('T', 'X', 3), ('T', 'Y', 6), ('U', 'X', 9), ('U', 'Y', 1),
             ('V', 'Z', 5), ('W', 'Z', 6), ('X', 'Z', 4), ('Y', 'Z', 7)
             ]


inf = float('inf')  # 无穷大

cloest_rout = [['A']]

S = {'A': 0}  # 确定最短路径集合

U = {'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf, 'G': inf,'H': inf,'I': inf,'J': inf, 'K': inf, 'L': inf, 'M': inf, 'N': inf, 'O': inf,'P': inf,'Q': inf,
        'R': inf, 'S': inf, 'T': inf, 'U': inf, 'V': inf, 'W': inf, 'X': inf, 'Y': inf,'Z': inf }  # 未确定的最短路径集合

while (U != {}):  # 直到未确定最短路径为空，才最终确定完最短路径

    findCloestrout(inf, rout, S, U, cloest_rout)

list1 = cloest_rout[-1]
print('Start-End最短路径为:')
print(list1[-1] + ':', end='')
print('->'.join(list1))
print('Start-End最短路径长度为：', S['Z'])