Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- INF = float('inf')
- G = [[INF, 7, INF, 5, INF, INF, INF],
- [7, INF, 8, 9, 7, INF, INF],
- [INF, 8, INF, INF, 5, INF, INF],
- [5, 9, INF, INF, 15, 6, INF],
- [INF, 7, 5, 15, INF, 8, 9],
- [INF, INF, INF, 6, 8, INF, 11],
- [INF, INF, INF, INF, 9, 11, INF]]
- N = len(G)
- used = [False] * N
- min_weight_edge = [INF] * N
- end_min_edge = [-1] * N
- min_weight_edge[0] = 0
- for i in range(N):
- v = -1
- for j in range(N):
- if(not used[j] and (v == -1 or min_weight_edge[j] < min_weight_edge[v])):
- v = j
- used[v] = True
- if(end_min_edge[v] != -1):
- print(v, end_min_edge[v])
- for c in range(N):
- if(not used[c] and G[v][c] < min_weight_edge[c]):
- min_weight_edge[c] = G[v][c]
- end_min_edge[c] = v
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement