dijkstra implementation with the help of priority queue in python

Solutions on MaxInterview for dijkstra implementation with the help of priority queue in python by the best coders in the world

Search
showing results for - "dijkstra implementation with the help of priority queue in python"
Rafael
22 Jan 2016
1import heapq
2
3
4def calculate_distances(graph, starting_vertex):
5    distances = {vertex: float('infinity') for vertex in graph}
6    distances[starting_vertex] = 0
7
8    pq = [(0, starting_vertex)]
9    while len(pq) > 0:
10        current_distance, current_vertex = heapq.heappop(pq)
11
12        # Nodes can get added to the priority queue multiple times. We only
13        # process a vertex the first time we remove it from the priority queue.
14        if current_distance > distances[current_vertex]:
15            continue
16
17        for neighbor, weight in graph[current_vertex].items():
18            distance = current_distance + weight
19
20            # Only consider this new path if it's better than any path we've
21            # already found.
22            if distance < distances[neighbor]:
23                distances[neighbor] = distance
24                heapq.heappush(pq, (distance, neighbor))
25
26    return distances
27
28
29example_graph = {
30    'U': {'V': 2, 'W': 5, 'X': 1},
31    'V': {'U': 2, 'X': 2, 'W': 3},
32    'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
33    'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
34    'Y': {'X': 1, 'W': 1, 'Z': 1},
35    'Z': {'W': 5, 'Y': 1},
36}
37print(calculate_distances(example_graph, 'X'))
38# => {'U': 1, 'W': 2, 'V': 2, 'Y': 1, 'X': 0, 'Z': 2}
39
source
similar questions
python get item from queuepython dijkstra implementation stackpython list as queuepython list as stack and queuequeues in pythonstck overflow python queuepython queue priority queuequeue in pythonpython priority queuepriority queue in python
queries leading to this page
implement dijkstra 27s algorithm using priority queuedijkstra 27s algorithm with priority queue in pythondijkstra 27s algorithm python priority queuedijkstra algorithm python using priority queuepriority queue in dijkstrahow many priority queue operations are involved in dijkstra algorithmdijkstra 27s algorithm priority queuedijkstra algorithm using priority queue javadijkstra using priority queue javadijkstra with priority queueusing dijkstra and priority queuedijkstra with priority queue python implementationdijkstra algorithm using priority queue using javapriority queue in dijkstra program implementationdijkstra algorithm code using priority queueis priority queue necessary in dijkstra algorithmpriority queue and dijkstra algorithm workingdijkstra java priority queuedijkstra java code with priority queuepython dijkstra priority queuequeue or priority queue in dijkstradijkstra algorithm with priority queuedijkstra 27s algorithm java priority queuedijkstra priority queuedijkstra algorithm using priority queuedijkstra 27s priority queue dijkstra using priority queuejava dijkstra priority queuepriority queue in python dijkstradoes dijkstra use a priority queuedijkstra algorithmus priority queuedijkstra priority queue javapriority queue dijkstradoes dijkstra algorithm using priority queueusing priority queue in dijkstradijkstra 27s algorithm using priority queuedijkstra algorithm using priority queue pythondijkstra algorithm java priority queuedijkstra algorithm priority queue javadijkstra 27s algorithm java using priority queue stubdijkstra priority queue pythondijkstra 27s using priority queuehow many priority queue operations are involved in dijkstra e2 80 99s algorithm 3fdijkstra algorithm priority queuewhy do we need to use priority queue in dijkstra algorithmdijkstra 27s algorithm java using priority queuedijkstra 27s algorithm with priority queue pythondijkstra 27s algorithm with priority queuedijkstra implementation with the help of priority queue in python