1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| def dijstra(s): global n global cost len = [1000 for i in range(n)] visit = [0 for i in range(n)]
for i in range(n): len[i] = cost[s][i] visit[i] = 0 visit[s] = 1
for i in range(n-1): min = 10000 for j in range(n): if (visit[j]==0 and min>len[j]): min = len[j] pos = j
visit[pos] = 1
for j in range(n): if (visit[j] == 0 and len[j]>len[pos] + cost[pos][j]): len[j] = len[pos] + cost[pos][j]
print(len)
def floyd(): global n global cost path = [[0 for i in range(n)]for j in range(n)] length = [[0 for i in range(n)]for j in range(n)] for i in range(n): for j in range(n): length[i][j] = cost[i][j] if cost[i][j] < 1000: path[i][j] = i else: path[i][j] = -1
for k in range(n): for i in range(n): for j in range(n): if (length[i][k] < 1000)and (length[k][j] < 1000): if (length[i][j] > length[i][k] + length[k][j]): length[i][j] = length[i][k] + length[k][j] path[i][j] = k for i in range(n): print(length[i])
global n n = int(input('Please input the number of notes: ')) cost = [] for i in range(n): cost.append(list(map(int, input().split(' '))))
s = int(input('Please input the source: ')) dijstra(s)
input('Please run floyd') floyd()
|