davegimo

dijkstra

Jan 30th, 2021
596
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. inf = float("inf")
  2.  
  3. def createGraph(n):
  4.     M = []
  5.     for i in range(n):
  6.         M.append([])
  7.         for j in range(n):
  8.             M[i].append(inf)
  9.     return M
  10.  
  11.  
  12. def size(G):
  13.     return len(G)
  14.  
  15.  
  16. def insert(G, i, j, w):
  17.     G[i][j] = w
  18.  
  19.  
  20. def delete(G, i, j):
  21.     G[i][j] = inf
  22.  
  23.  
  24. def isEdge(G, i, j):
  25.     return G[i][j] != []
  26.  
  27.  
  28. def weight(G, i, j):
  29.     return G[i][j]
  30.  
  31.  
  32. def getAdjacents(G, i):
  33.     V = []
  34.     for j in range(len(G)):
  35.         if G[i][j] != inf:
  36.             V.append([j, G[i][j]])
  37.     return V
  38.  
  39.  
  40. def minVertex(D, V):
  41.     min = inf
  42.     y = -1
  43.     for i in range(len(D)):
  44.         if (not V[i]) and (D[i] < min):
  45.             y = i
  46.             min = D[i]
  47.     return y
  48.  
  49.  
  50. def Dijkstra(G, s):
  51.     n = size(G)
  52.  
  53.     dist = []
  54.     visited = []
  55.  
  56.     for i in range(n):
  57.         dist.append(inf)
  58.         visited.append(False)
  59.  
  60.     dist[s] = 0
  61.  
  62.     for i in range(n - 1):
  63.         next = minVertex(dist, visited)
  64.         visited[next] = True
  65.  
  66.         V = getAdjacents(G, next)
  67.         for [z, w] in V:
  68.             d = dist[next] + w
  69.             if dist[z] > d:
  70.                 dist[z] = d
  71.  
  72.     return dist
  73.  
  74.  
  75. ########################
  76.  
  77. G = createGraph(6)
  78.  
  79. insert(G, 0, 1, 2)
  80. insert(G, 0, 5, 9)
  81. insert(G, 1, 3, 8)
  82. insert(G, 1, 2, 6)
  83. insert(G, 1, 5, 5)
  84. insert(G, 2, 3, 1)
  85. insert(G, 4, 3, 3)
  86. insert(G, 4, 2, 7)
  87. insert(G, 5, 4, 3)
  88.  
  89.  
  90. D = Dijkstra(G, 0)
  91. print("")
  92. print(D[0])
  93. print(D[1])
  94.  
  95.  
  96.  
  97.  
RAW Paste Data