-
Notifications
You must be signed in to change notification settings - Fork 0
/
romanian_complete.py
79 lines (67 loc) · 2.58 KB
/
romanian_complete.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
78
79
import sys
from heapq import heapify, heappush, heappop
inf = sys.maxsize
class Romanian_DFS():
def __init__(self, graph, src, dest):
self.graph = graph
self.src = src
self.dest = dest
self.shortest_distance = []
self.shortest_path = []
self.new_nodes = []
def dfs_recursive(self, new_src):
if new_src not in self.new_nodes:
self.new_nodes.append(new_src)
neighbors = self.graph[new_src]
list_neighbors = list(neighbors.keys())
for i, neighbor in enumerate(list_neighbors):
self.dfs_recursive(neighbor)
return self.new_nodes
def create_node_data(self, nodes):
node_data = {node: {'cost': inf, 'pred': []} for node in nodes}
return node_data
def dijkstra(self):
if self.new_nodes == []:
self.dfs_recursive(self.src)
print(self.new_nodes)
node_data = self.create_node_data(self.new_nodes)
node_data[self.src]['cost'] = 0
visited = []
temp = self.src
for i in range(len(node_data)-1):
if temp not in visited:
visited.append(temp)
min_heap = []
for j in self.graph[temp]:
if j not in visited:
cost = node_data[temp]['cost'] + self.graph[temp][j]
if cost < node_data[j]['cost']:
node_data[j]['cost'] = cost
node_data[j]['pred'] = node_data[temp]['pred'] + [temp]
heappush(min_heap, (node_data[j]['cost'], j))
heapify(min_heap)
temp = min_heap[0][1]
self.shortest_path = node_data[self.dest]['pred'] + [self.dest]
self.shortest_distance = node_data[self.dest]['cost']
print(f"Shortest Distance: {str(self.shortest_distance)}")
print(f"Shortest Path: {str(self.shortest_path)}" )
if __name__ == "__main__":
graph = {
'Amsterdam' : {'Beijing':2, 'Cairo':4},
'Beijing' : {'Amsterdam':2, 'Cairo':3, 'Dubai':8},
'Cairo' : {'Amsterdam':4, 'Beijing':3, 'Edinburgh':5, 'Dubai':2},
'Dubai' : {'Beijing':8,'Cairo':2,'Edinburgh':11,'Frankfurt':22},
'Edinburgh' : {'Cairo':5, 'Dubai':11, 'Frankfurt':1},
'Frankfurt' : {'Dubai':22, 'Edinburgh':1}
}
# graph1 = {
# 'Oradea':
# 'Zerind':
# 'Arad':
# 'Timisoara':
# ''
# }
source = 'Amsterdam'
dest = 'Frankfurt'
romanian_1 = Romanian_DFS(graph, source, dest)
romanian_1.dijkstra()