-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithm.py
49 lines (43 loc) · 1.37 KB
/
algorithm.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
def search_min_path(graph: dict, initial: str='START', destination: str='END') -> list:
path = {}
adj_node = {}
queue = []
result = []
for node in graph:
path[node] = float("inf")
adj_node[node] = None
queue.append(node)
path[initial] = 0
while queue:
# find min distance which wasn't marked as current
key_min = queue[0]
min_val = path[key_min]
for n in range(1, len(queue)):
if path[queue[n]] < min_val:
key_min = queue[n]
min_val = path[key_min]
cur = key_min
queue.remove(cur)
for i in graph[cur]:
alternate = graph[cur][i] + path[cur]
if path[i] > alternate:
path[i] = alternate
adj_node[i] = cur
result.append(destination)
while True:
destination = adj_node[destination]
if destination is None:
break
result.append(destination)
return result[::-1]
if __name__ == "__main__":
graph = {
'START': {'2_1': 2, '2_2': 5},
'2_1': {'2_2': 5, '3_1': 4, '3_2': 8},
'2_2': {'2_1': 2, '3_2': 8, '3_3': 2},
'3_1': {'3_2': 8, 'END': 7},
'3_2': {'3_1': 4, '3_3': 2, 'END': 7},
'3_3': {'3_2': 8, 'END': 7},
'END': {}
}
print(search_min_path(graph))