Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. INF = float('inf')
  2.  
  3. G = [[INF, 7, INF, 5, INF, INF, INF],
  4.     [7, INF, 8, 9, 7, INF, INF],
  5.     [INF, 8, INF, INF, 5, INF, INF],
  6.     [5, 9, INF, INF, 15, 6, INF],
  7.     [INF, 7, 5, 15, INF, 8, 9],
  8.     [INF, INF, INF, 6, 8, INF, 11],
  9.     [INF, INF, INF, INF, 9, 11, INF]]
  10.  
  11. N = len(G)
  12.  
  13. used = [False] * N
  14. min_weight_edge = [INF] * N
  15. end_min_edge = [-1] * N
  16. min_weight_edge[0] = 0
  17.  
  18. for i in range(N):
  19.     v = -1
  20.     for j in range(N):
  21.         if(not used[j] and (v == -1 or min_weight_edge[j] < min_weight_edge[v])):
  22.             v = j
  23.     used[v] = True
  24.     if(end_min_edge[v] != -1):
  25.         print(v, end_min_edge[v])
  26.    
  27.     for c in range(N):
  28.         if(not used[c] and G[v][c] < min_weight_edge[c]):
  29.             min_weight_edge[c] = G[v][c]
  30.             end_min_edge[c] = v
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement