Weighted Shortest Paths

Always expand the closest node

With non-negative edge weights, Dijkstra's algorithm repeatedly takes the closest unsettled node from a min-heap and relaxes its edges. Skipping stale heap entries keeps it correct with a simple heap. Complexity is O((V + E) log V). Negative weights need Bellman-Ford; edges with weights 0 or 1 can use a deque (0-1 BFS).

Shortest distances from A, run

I ran this with Python 3.12.3 (standard library only). The direct edge A to B costs 4, but A to C to B costs 3, and D is reached at cost 4 through B.

# Dijkstra's shortest paths with a heap (non-negative weights)
import heapq

def dijkstra(graph, src):
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                      # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

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

Output:

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

Check for negative weights

Ask whether weights can be negative before choosing Dijkstra.

त्वरित जाँच: When does Dijkstra's algorithm fail?

• When there are more than 100 nodes
• When the graph is directed
• When weights are integers
• When the graph has negative edge weights