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