Dijkstra and nonnegative weights

What is a weighted graph?

A weighted graph attaches a number to each edge, such as a distance, cost, or travel time. A path is a sequence of connected edges; its total cost is the sum of their weights. A shortest-path algorithm finds the least total cost under the problem’s rules. Different rules, especially negative weights, require different algorithms.

Example: A → B costs 4 and B → C costs 3, so that route costs 7. If A → C costs 10, the route through B is cheaper even though it uses more edges.

Helpful before this chapter

If these ideas are new, begin with:

Heaps and priority queues Graph representations and traversal Graph ordering and connectivity

Understand the idea

Dijkstra repeatedly extracts the smallest tentative distance. Nonnegative edges guarantee that no later path through an unsettled node can reduce that settled distance. Lazy heaps must skip outdated entries.

Work through an example

A→B costs 4, A→C costs 1, C→B costs 2. Settle C first, improve B to 3, and ignore B's stale cost-4 entry.

Time and space complexity

Lazy heap O((V+E) log(V+E)) time/O(V+E) storage; often written O(E log V) for simple connected graphs.

Why it works

An extracted non-stale minimum is a final shortest distance when all weights are nonnegative.

Common mistakes

Negative edges invalidate finalization.
Heap tuples need comparable tie fields or a separate counter for arbitrary node objects.

Chapter lab · Python implementation

Weighted objectives require precise distinctions. Dijkstra finds cheapest routes from one source with nonnegative weights. Bellman-Ford permits negative edges and detects reachable negative cycles. A minimum spanning tree minimizes the total edges needed to connect all vertices; it does not minimize every source-to-vertex route.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

import heapq

def dijkstra(graph,start):
    if any(w<0 for edges in graph.values() for _,w in edges):
        raise ValueError('nonnegative weights required')
    distances={start:0}; heap=[(0,start)]
    while heap:
        cost,node=heapq.heappop(heap)
        if cost!=distances[node]: continue
        for neighbor,weight in graph.get(node,[]):
            candidate=cost+weight
            if candidate<distances.get(neighbor,float('inf')):
                distances[neighbor]=candidate
                heapq.heappush(heap,(candidate,neighbor))
    return distances

def bellman_ford(n,edges,start):
    d=[float('inf')]*n; d[start]=0
    for _ in range(n-1):
        changed=False
        for a,b,w in edges:
            if d[a]!=float('inf') and d[a]+w<d[b]:
                d[b]=d[a]+w; changed=True
        if not changed: break
    if any(d[a]!=float('inf') and d[a]+w<d[b] for a,b,w in edges):
        raise ValueError('reachable negative cycle')
    return d

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':[('B',4),('C',1)],'C':[('B',2)],'B':[]}
assert dijkstra(g,'A')=={'A':0,'B':3,'C':1}
assert bellman_ford(3,[(0,1,4),(0,2,1),(2,1,-2)],0)==[0,-1,1]
try: bellman_ford(2,[(0,1,-1),(1,0,-1)],0)
except ValueError: pass
else: raise AssertionError('negative cycle not detected')

CHECK YOUR UNDERSTANDING

What is a weighted graph?

Initialize source A.