davegimo

Untitled

Jun 7th, 2020
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def Dijkstra(G,s):
  2. n = size(G)
  3. dist = []
  4. pred = []
  5. visited = []
  6. listaRistoranti = []
  7.  
  8.  
  9. for i in range(n):
  10. dist.append(inf)
  11. visited.append(False)
  12. pred.append(-1)
  13. dist[s] = 0
  14.  
  15.  
  16. for i in range(n-1):
  17. next = minVertex(dist,visited)
  18. visited[next] = True
  19.  
  20. if kind(G,next) == "R":
  21. listaRistoranti.append(next)
  22. if len(listaRistoranti) == 3:
  23. return listaRistoranti
  24.  
  25. V = neighbors(G,next) #lista degli adiacenti di next
  26.  
  27. for [z,w] in V:
  28. d = dist[next] + w
  29. if (dist[z] > d):
  30. dist[z] = d
  31. pred[z] = next
  32.  
  33. return listaRistoranti
  34.  
  35.  
  36.  
  37.  
  38. def Dijkstra(G,s,destination,k):
  39. n = size(G)
  40. dist = []
  41. pred = []
  42. visited = []
  43. for i in range(n):
  44. dist.append(inf)
  45. visited.append(False)
  46. pred.append(-1)
  47. dist[s] = 0
  48.  
  49.  
  50. for i in range(n-1):
  51. next = minVertex(dist,visited)
  52. visited[next] = True
  53. if next == destination:
  54. if dist[next] <= k:
  55. return True
  56. else:
  57. return False
  58.  
  59. V = neighbors(G,next)
  60. for [z,w] in V:
  61. d = dist[next] + w
  62. if (dist[z] > d):
  63. dist[z] = d
  64. pred[z] = next
  65.  
  66. return False
RAW Paste Data