Dijkstra Algorithm

Dijkstra Shortest Path

import heapq

# Shortest path in weighted graph (non-negative edges)
# O((V+E) log V)

def dijkstra(graph, start):
    # graph = {node: [(weight, neighbour), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]: continue  # stale entry
        for weight, nb in graph[node]:
            new_d = d + weight
            if new_d < dist[nb]:
                dist[nb] = new_d
                heapq.heappush(heap, (new_d, nb))
    return dist

graph = {
    'A': [(1,'B'),(4,'C')],
    'B': [(2,'C'),(5,'D')],
    'C': [(1,'D')],
    'D': []
}
print(dijkstra(graph, 'A'))
# {'A':0,'B':1,'C':3,'D':4}

# Bellman-Ford -- handles negative edges O(VE)
# Floyd-Warshall -- all pairs shortest path O(V^3)