-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.py
78 lines (55 loc) · 2.29 KB
/
dijkstra.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import sys
import heapq
import networkx as nx
class dijkstra:
def __init__(self, G):
# vytvorime deep copy grafu
self.graph = G.copy()
self.pos = nx.get_node_attributes(G, "pos")
self.name = "dijkstra"
def get_path(self, source, target):
path = []
path.append(target)
while target != source:
target = self.graph.node[target]["previous"]
path.append(target)
path.reverse()
return path
def get_path_length(self, path):
# funkcia ktora vrati dlzku trasy
try:
sz = len(path)
cost = 0
for i in range(0, sz - 2):
cost += self.graph.get_edge_data(path[i], path[i + 1])["weight"]
cost += self.graph.get_edge_data(path[sz - 2], path[sz - 1])["weight"]
except TypeError:
pass
return cost
def shortest_path(self, source, target):
# nastavenie defaultnych atributov pre vsetky uzly v grafe
nx.set_node_attributes(self.graph, None, "previous")
nx.set_node_attributes(self.graph, sys.maxsize, "dist")
nx.set_node_attributes(self.graph, False, "visited")
visited = []
queue = []
# pociatocny uzol = source, cize vzdialenost = 0
self.graph.node[source]["dist"] = 0
# vytvorenie zoznamu s priority algoritmom
heapq.heappush(queue, (0, source))
while len(queue) != False:
# z priority zasobniku vyberieme aktualny uzol
current = heapq.heappop(queue)
self.graph.node[current[1]]["visited"] = True
visited.append(current[1])
for neighbor in self.graph.neighbors(current[1]):
if self.graph.node[neighbor]["visited"] == False:
distfromstart = (
self.graph.node[current[1]]["dist"]
+ self.graph.get_edge_data(current[1], neighbor)["weight"]
)
if distfromstart < self.graph.node[neighbor]["dist"]:
self.graph.node[neighbor]["dist"] = distfromstart
self.graph.node[neighbor]["previous"] = current[1]
heapq.heappush(queue, (distfromstart, neighbor))
return self.get_path(source, target)