迪杰斯特拉（Dijkstra)算法Python实现

import numpy as npdef Input_Fun():n = int(input().strip())weight = []for i in range(n):temp = input().split(' ')for j in temp:weight.append(int(j))weights = np.array(weight).reshape(n, n)print(n)print(weights)return n, weightsdef Result_Output(prev, i):if prev[i] != 0:Result_Output(prev, prev[i])print('->{}'.format(prev[i]+1), end='')def Dijkstra():n, weights = Input_Fun()flag = np.zeros(n, bool)  # 设置标志，确认是否加入集合dist = weights[0]  # 记录第0点到各个位置的距离prev = np.zeros(n, int)  # 记录节点的前一个位置for i in range(n - 1):  # 进行n-1次迭代，每次加入一个点temp = float('inf')u = 0for j in range(n):if not flag[j] and dist[j] < temp and dist[j] != 0:  # 该点不在集合内、距离小、有连接u = jtemp = dist[j]flag[u] = Truefor j in range(n):if not flag[j] and weights[u][j] != 0:if dist[u] + weights[u][j] < dist[j] or dist[j] == 0:dist[j] = dist[u] + weights[u][j]prev[j] = ufor i in range(n - 1):print(dist[i + 1], ':1', end='')Result_Output(prev, i+1)print("->{}".format(i + 2))if __name__ == '__main__':Dijkstra()