python dijkstra implementation stack

Solutions on MaxInterview for python dijkstra implementation stack by the best coders in the world

showing results for - "python dijkstra implementation stack"
Odele
19 Oct 2020
1nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
2distances = {
3    'B': {'A': 5, 'D': 1, 'G': 2},
4    'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
5    'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
6    'G': {'B': 2, 'D': 1, 'C': 2},
7    'C': {'G': 2, 'E': 1, 'F': 16},
8    'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
9    'F': {'A': 5, 'E': 2, 'C': 16}}
10
11unvisited = {node: None for node in nodes} #using None as +inf
12visited = {}
13current = 'B'
14currentDistance = 0
15unvisited[current] = currentDistance
16
17while True:
18    for neighbour, distance in distances[current].items():
19        if neighbour not in unvisited: continue
20        newDistance = currentDistance + distance
21        if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
22            unvisited[neighbour] = newDistance
23    visited[current] = currentDistance
24    del unvisited[current]
25    if not unvisited: break
26    candidates = [node for node in unvisited.items() if node[1]]
27    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
28
29print(visited)