Dijkstra's Shortest Path Algorithm

In unweighted graphs, BFS finds the shortest path. But many real-world graphs have weighted edges — roads have distances, network links have latencies, and pipelines have capacities. Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a graph with non-negative edge weights.

---

The Problem

Given a weighted graph and a source vertex, find the shortest (minimum total weight) path from the source to every other vertex.

Example: In a road network, find the shortest driving distance from your home to every other location.

---

How Dijkstra's Algorithm Works

Dijkstra's algorithm maintains a distance table and a priority queue (or a simple unvisited set). It works as follows:

1. Set the distance to the source as 0 and to all other vertices as infinity (∞).
2. Mark all vertices as unvisited.
3. Select the unvisited vertex with the smallest distance (initially the source).
4. For each unvisited neighbour of the current vertex:
   • Calculate the tentative distance = current vertex's distance + edge weight.
   • If this is less than the neighbour's recorded distance, update it.
5. Mark the current vertex as visited.
6. Repeat from step 3 until all vertices are visited (or the target is reached).

---

Pseudocode

PROCEDURE Dijkstra(graph, source)
    FOR EACH vertex v IN graph
        dist[v] = INFINITY
        previous[v] = NULL
        visited[v] = FALSE
    END FOR
    dist[source] = 0

    REPEAT V times:
        u = unvisited vertex with smallest dist[u]
        visited[u] = TRUE

        FOR EACH neighbour v OF u
            IF NOT visited[v] THEN
                newDist = dist[u] + weight(u, v)
                IF newDist < dist[v] THEN
                    dist[v] = newDist
                    previous[v] = u
                END IF
            END IF
        END FOR
    END REPEAT
END PROCEDURE

---

Trace Example

Consider this weighted graph:

    A --4-- B
    |       |
    2       1
    |       |
    C --3-- D --5-- E

Edges: A-B (4), A-C (2), B-D (1), C-D (3), D-E (5)

Find shortest paths from A to all vertices.

Initial State

Vertex	Distance	Previous	Visited
A	0	—	No
B	∞	—	No
C	∞	—	No
D	∞	—	No
E	∞	—	No

Step 1: Process A (smallest distance = 0)

Check neighbours: B (0+4=4), C (0+2=2)

Vertex	Distance	Previous	Visited
A	0	—	Yes
B	4	A	No
C	2	A	No
D	∞	—	No
E	∞	—	No

Step 2: Process C (smallest unvisited distance = 2)

Check neighbours: D (2+3=5)