Shortest Path Algorithms — Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson's, A* and 0-1 BFS (Interactive Simulator)

The Story — The Delivery Rider's Question

A shortest path is the path between two nodes with the smallest total weight. It is not always the path with the fewest edges. Three short roads can beat one long road.

The Six Algorithms at a Glance

Watch Dijkstra Work — Animated Diagram

Start node is A. Numbers on arrows are weights. The value under each node is its current best distance. Watch how B first gets 4, then improves to 3 through C. Crossed-out queue items are stale. They are old copies that get skipped.

The Shortest Path Simulator — Build Your Own Graph

This is your lab. Draw nodes and weighted edges, then pick any of the six algorithms. Each Step runs one line of the algorithm. You will see the priority queue, deque, edge list or matrix change. You also see the distance table and the current line of code.

A* vs Dijkstra — Grid Race

Games move characters on grids. Click cells to draw walls (drag to paint). Then press Race. Both algorithms find a shortest path of the same length. Green cells show how many cells each one had to explore.

Why Dijkstra Fails With Negative Weights

Dijkstra makes a promise. Once a node is taken from the queue, its distance is final. That promise is only true if no edge can make a path cheaper later. A negative edge breaks it.

Step-by-Step Traces

Dijkstra — Graph: A→B 4, A→C 1, C→B 2, C→D 5, B→D 1

Bellman-Ford — Edge order: B→D 2, A→B 4, A→C 5, C→B −3

Floyd-Warshall — 4 nodes, what each k changes

Python Implementation

1. Dijkstra (heapq)

import heapq

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

def dijkstra(graph, src):
    dist = {n: float('inf') for n in graph}
    prev = {n: None for n in graph}
    dist[src] = 0
    pq = [(0, src)]
    done = set()
    while pq:
        d, u = heapq.heappop(pq)      # smallest distance first
        if u in done:
            continue                    # stale entry
        done.add(u)
        for v, w in graph[u]:
            if d + w < dist[v]:          # relax
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, prev

def path(prev, t):
    p = []
    while t is not None:
        p.append(t)
        t = prev[t]
    return p[::-1]

dist, prev = dijkstra(graph, 'A')
print("Distances:", dist)
print("Path A->D:", " -> ".join(path(prev, 'D')))

2. Bellman-Ford (with negative cycle check)

def bellman_ford(nodes, edges, src):
    dist = {n: float('inf') for n in nodes}
    dist[src] = 0
    for i in range(len(nodes) - 1):     # V - 1 passes
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        print(f"Pass {i+1}: {dist}")
        if not changed:
            break                            # early stop
    for u, v, w in edges:                   # one extra check
        if dist[u] + w < dist[v]:
            raise ValueError("Negative cycle found!")
    return dist

nodes = ['A', 'B', 'C', 'D']
edges = [('B', 'D', 2), ('A', 'B', 4), ('A', 'C', 5), ('C', 'B', -3)]
print("Final:", bellman_ford(nodes, edges, 'A'))

try:
    bellman_ford(['X', 'Y', 'Z'],
                 [('X', 'Y', 1), ('Y', 'Z', -2), ('Z', 'Y', 1)], 'X')
except ValueError as e:
    print("Error:", e)

3. Floyd-Warshall

INF = float('inf')

def floyd_warshall(n, edges):
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):          # middle node
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d                        # d[i][i] < 0 means negative cycle

# nodes 1..4 stored as 0..3
edges = [(0,1,4), (1,2,2), (0,2,11), (2,0,3), (2,3,1), (3,1,-1)]
for row in floyd_warshall(4, edges):
    print(row)

4. Johnson's Algorithm

# uses bellman_ford (without prints) and dijkstra from above
def johnson(nodes, edges):
    q = '__q__'                                   # new helper node
    extra = [(q, v, 0) for v in nodes]
    h = bellman_ford(nodes + [q], edges + extra, q)  # step 1: potentials
    g = {u: [] for u in nodes}
    for u, v, w in edges:
        g[u].append((v, w + h[u] - h[v]))         # step 2: new weight >= 0
    result = {}
    for u in nodes:                              # step 3: Dijkstra from each
        d, _ = dijkstra(g, u)
        result[u] = {v: d[v] - h[u] + h[v] for v in nodes}
    return h, result

h, res = johnson(nodes, edges)    # same graph as Bellman-Ford
print("h:", {k: v for k, v in h.items() if k != '__q__'})
for u in nodes:
    print(u, res[u])

5. A* Search

import heapq, math

pos = {'S': (0, 0), 'A': (2, 1), 'B': (1, 3), 'C': (4, 2), 'G': (5, 4)}
graph = {'S': [('A', 3), ('B', 4)], 'A': [('C', 3), ('B', 3)],
         'B': [('G', 6)], 'C': [('G', 3)], 'G': []}

def h(n, goal):                         # straight-line guess
    (x1, y1), (x2, y2) = pos[n], pos[goal]
    return math.hypot(x1 - x2, y1 - y2)

def a_star(graph, start, goal):
    g = {start: 0}
    prev = {start: None}
    open_pq = [(h(start, goal), start)]   # (f, node)
    closed, expanded = set(), []
    while open_pq:
        f, u = heapq.heappop(open_pq)
        if u in closed:
            continue
        expanded.append(u)
        if u == goal:                      # stop at the goal
            return g[u], path(prev, goal), expanded
        closed.add(u)
        for v, w in graph[u]:
            if g[u] + w < g.get(v, float('inf')):
                g[v] = g[u] + w
                prev[v] = u
                heapq.heappush(open_pq, (g[v] + h(v, goal), v))
    return float('inf'), [], expanded

print(a_star(graph, 'S', 'G'))

6. 0-1 BFS (deque)

from collections import deque

graph = {0: [(1, 0), (2, 1)], 1: [(3, 1)], 2: [(3, 0)], 3: [(4, 1)], 4: []}

def zero_one_bfs(graph, src):
    dist = {n: float('inf') for n in graph}
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)   # same distance: FRONT
                else:
                    dq.append(v)       # one more: BACK
    return dist

print(zero_one_bfs(graph, 0))

Time and Space Complexity

V = number of nodes. E = number of edges.

Which Algorithm Should I Use? — Interactive Chooser

Answer the questions. The chooser picks the best algorithm for your problem.

Where These Algorithms Are Used

Golden Rules