Dijkstra's Shortest Path Algorithm

Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph (where all edge weights are non-negative).

Comparison: Dijkstra vs. Prim

Dijkstra's algorithm is structurally very similar to Prim's MST algorithm. Both are greedy, use key-value updates, and finalize one vertex per step. However, they solve fundamentally different problems:

Feature	Prim's Algorithm	Dijkstra's Algorithm
Goal	Find the tree that connects all vertices with the minimum total edge weight (MST).	Find the path from a source vertex to all other vertices with the minimum total path distance.
Relaxation Formula	`key[v] = min(key[v], weight(u, v))`	`dist[v] = min(dist[v], dist[u] + weight(u, v))`

The Algorithm Steps

Create a dist array of size $V$ where dist[i] holds the shortest distance from the source to vertex i. Initialize all values as Infinity, except dist[source] = 0.
Create a boolean array sptSet (Shortest Path Tree Set) of size $V$ to keep track of vertices whose shortest distance from the source is finalized. Initialize all as false.
Loop $V - 1$ times:
- Pick a vertex $u$ that is not in sptSet and has the minimum distance value in the dist array.
- Include $u$ in sptSet (sptSet[u] = true).
- Update the dist values of all adjacent neighbors of $u$: for each neighbor $v$, if $v$ is not in sptSet and dist[u] + weight(u, v) < dist[v], update dist[v] = dist[u] + weight(u, v).

Visual Example Walkthrough

Let's find the shortest path from source 0 to all other vertices:

Trace Table (Source = 0)

Vertex	Distance from Source	Explanation
0	0	Source vertex starts at distance 0.
1	4	Path: `0 -> 1`
2	12	Path: `0 -> 1 -> 2`
3	19	Path: `0 -> 1 -> 2 -> 3`
4	21	Path: `0 -> 7 -> 6 -> 5 -> 4` (11 + 10 = 21)
5	11	Path: `0 -> 7 -> 6 -> 5` (8 + 1 + 2 = 11)
6	9	Path: `0 -> 7 -> 6` (8 + 1 = 9)
7	8	Path: `0 -> 7`
8	14	Path: `0 -> 1 -> 2 -> 8` (12 + 2 = 14)

JavaScript Code Implementation

class WeightedGraph {
    constructor(verticesCount) {
        this.vertices = verticesCount;
        this.adj = Array.from({ length: verticesCount }, () => []);
    }
 
    addEdge(u, v, weight) {
        this.adj[u].push({ node: v, weight: weight });
        this.adj[v].push({ node: u, weight: weight });
    }
 
    // Dijkstra's Algorithm
    dijkstra(src) {
        const dist = new Array(this.vertices).fill(Infinity);
        const sptSet = new Array(this.vertices).fill(false);
 
        // Distance from source to itself is always 0
        dist[src] = 0;
 
        for (let count = 0; count < this.vertices - 1; count++) {
            // Pick the minimum distance vertex from the set of vertices not yet processed
            const u = this._minDistance(dist, sptSet);
 
            // Mark the picked vertex as processed
            sptSet[u] = true;
 
            // Update dist value of the adjacent vertices of the picked vertex
            for (let edge of this.adj[u]) {
                const v = edge.node;
                const weight = edge.weight;
 
                // Update dist[v] only if it is not in sptSet and total weight of path is smaller than current dist[v]
                if (!sptSet[v] && dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
 
        this._printSolution(dist);
    }
 
    // Helper to find the vertex with the minimum distance value
    _minDistance(dist, sptSet) {
        let min = Infinity;
        let minIndex = -1;
 
        for (let v = 0; v < this.vertices; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
 
    // Helper to print the output distances
    _printSolution(dist) {
        console.log("Vertex \t Distance from Source");
        for (let i = 0; i < this.vertices; i++) {
            console.log(`${i} \t\t ${dist[i]}`);
        }
    }
}
 
// Driver code matching the example graph
const g = new WeightedGraph(9);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
 
g.dijkstra(0);
/*
Output:
Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14
*/

Complexity Analysis

Time Complexity:
- $O(V^2)$ using adjacency matrix or simple array lookup (as implemented above).
- $O(E \log V)$ if implemented using an Adjacency List and a Binary Min-Heap / Priority Queue to retrieve the next vertex.
Space Complexity: $O(V)$
- To store distance tracking and sptSet arrays.

Prim's MST Algorithm Bellman-Ford Algorithm