Skip to content

Instantly share code, notes, and snippets.

@calthoff
Created April 11, 2021 18:27
Show Gist options
  • Save calthoff/c145b9aa39cb76c4c239015948a000c1 to your computer and use it in GitHub Desktop.
Save calthoff/c145b9aa39cb76c4c239015948a000c1 to your computer and use it in GitHub Desktop.
import heapq
def dijkstra(graph, starting_vertex):
distances = {vertex: float('infinity') for vertex in graph}
distances[starting_vertex] = 0
pq = [(0, starting_vertex)]
while len(pq) > 0:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
graph = {
'U': {'V': 2, 'W': 5, 'X': 1},
'V': {'U': 2, 'X': 2, 'W': 3},
'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
'Y': {'X': 1, 'W': 1, 'Z': 1},
'Z': {'W': 5, 'Y': 1},
}
print(dijkstra(graph, 'Z'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment