Dijkstra's Algorithm - 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 with non-negative edge weights. It is one of the most famous and widely used algorithms in computer science.

Think of it like using Google Maps to find the shortest driving distance from your current location to every other city on the map. The algorithm explores the graph systematically, always choosing the next closest vertex to expand.

Key Properties

• Greedy algorithm – makes the locally optimal choice at each step.
• Works only for graphs with non-negative edge weights.
• Finds the shortest path from a source to all other vertices.
• Single-source shortest path (SSSP) algorithm.

Why Non-Negative Weights?

Dijkstra's algorithm relies on the assumption that once a vertex is finalized (its shortest distance is known), no later path through other vertices can improve it. This is only true if all edge weights are non-negative. If negative edges exist, the algorithm can fail, and we need Bellman-Ford instead.

How Dijkstra's Algorithm Works?

Step-by-Step Process

1. Initialize:
   • Set the distance to the source vertex as 0 and to all other vertices as ∞ (infinity).
   • Mark all vertices as unvisited.
2. Select: Pick the unvisited vertex with the minimum distance.
3. Relax: For each neighbor of the selected vertex, check if the path through the selected vertex gives a shorter distance. If yes, update the distance.
4. Mark: Mark the selected vertex as visited (finalized).
5. Repeat steps 2-4 until all vertices are visited.

Detailed Example

Consider the following weighted directed graph:

         (1)
    A -------- B
    | \       / |
    |  (4)  (2) |
    |   \   /   |
   (3)   C     (5)
    |   / \     |
    | (6) (7)   |
    | /     \   |
    D -------- E
         (8)

We want to find the shortest path from vertex A to all other vertices.

Step-by-Step Execution

Step 1: Initialization

Step 2: Select unvisited vertex with minimum distance = A (0)

• Relax neighbors of A:
  • B: 0 + 1 = 1 < ∞ → dist[B] = 1
  • C: 0 + 4 = 4 < ∞ → dist[C] = 4
  • D: 0 + 3 = 3 < ∞ → dist[D] = 3
• Mark A as visited.

Step 3: Select unvisited vertex with minimum distance = B (1)

• Relax neighbors of B:
  • C: 1 + 2 = 3 < 4 → dist[C] = 3
  • E: 1 + 5 = 6 < ∞ → dist[E] = 6
• Mark B as visited.

Step 4: Select unvisited vertex with minimum distance = C or D (3)
Let's pick C first.

• Relax neighbors of C:
  • D: 3 + 6 = 9 > 3 → No update
  • E: 3 + 7 = 10 > 6 → No update
• Mark C as visited.

Step 5: Select unvisited vertex with minimum distance = D (3)

• Relax neighbors of D:
  • E: 3 + 8 = 11 > 6 → No update
• Mark D as visited.

Step 6: Select unvisited vertex with minimum distance = E (6)

• No outgoing edges to relax.
• Mark E as visited.

Final Shortest Distances

Shortest Paths

• A → B: A-B (1)
• A → C: A-B-C (1 + 2 = 3)
• A → D: A-D (3)
• A → E: A-B-E (1 + 5 = 6)

Algorithm for Dijkstra's Algorithm

Pseudocode

Dijkstra(Graph G, source):
    Input:  G - Weighted graph with non-negative edge weights
            source - Starting vertex
    Output: dist[] - Shortest distances from source

    Step 1: dist[source] = 0
    Step 2: FOR each vertex v != source DO
    Step 3:     dist[v] = ∞
    Step 4: visited[] = false
    
    Step 5: FOR i = 0 to V-1 DO
    Step 6:     u = vertex with minimum dist among unvisited vertices
    Step 7:     visited[u] = true
    Step 8:     FOR each neighbor v of u DO
    Step 9:         IF visited[v] == false AND dist[u] + weight(u,v) < dist[v] THEN
    Step 10:            dist[v] = dist[u] + weight(u,v)
    Step 11:        END IF
    Step 12:     END FOR
    Step 13: END FOR
    Step 14: RETURN dist

Implementation in C (Adjacency Matrix)

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 5  // Number of vertices

// Function to find the unvisited vertex with minimum distance
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, min_index;
    
    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// Function to print the shortest distances
void printDistances(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

// Dijkstra's Algorithm
void dijkstra(int graph[V][V], int source) {
    int dist[V];        // Array to store shortest distances
    bool visited[V];    // Array to track visited vertices
    
    // Initialize distances as INFINITE and visited as false
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    
    // Distance from source to itself is always 0
    dist[source] = 0;
    
    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum distance vertex from unvisited vertices
        int u = minDistance(dist, visited);
        visited[u] = true;
        
        // Update dist values of adjacent vertices
        for (int v = 0; v < V; v++) {
            // Update dist[v] only if:
            // 1. v is not visited
            // 2. There is an edge from u to v
            // 3. Total weight of path from source to v through u is smaller
            if (!visited[v] && graph[u][v] && 
                dist[u] != INT_MAX && 
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    
    printDistances(dist);
}

int main() {
    // Adjacency matrix representation
    // 0 means no edge
    int graph[V][V] = {
        {0, 1, 4, 3, 0},
        {0, 0, 2, 0, 5},
        {0, 0, 0, 6, 7},
        {0, 0, 0, 0, 8},
        {0, 0, 0, 0, 0}
    };
    
    printf("Shortest distances from vertex 0:\n");
    dijkstra(graph, 0);
    
    return 0;
}

Output:

Shortest distances from vertex 0:
Vertex   Distance from Source
0        0
1        1
2        3
3        3
4        6

Implementation in C (Adjacency List with Binary Heap)

For sparse graphs, using an adjacency list with a binary heap gives better performance.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

// Adjacency List Node
typedef struct Node {
    int vertex;
    int weight;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int vertices;
    Node** adjLists;
} Graph;

// Min Heap Node
typedef struct HeapNode {
    int vertex;
    int dist;
} HeapNode;

// Min Heap
typedef struct MinHeap {
    int size;
    int capacity;
    int* position;
    HeapNode** array;
} MinHeap;

// Create a graph
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Add directed edge
void addEdge(Graph* graph, int src, int dest, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->weight = weight;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// Create a min heap node
HeapNode* createHeapNode(int vertex, int dist) {
    HeapNode* heapNode = (HeapNode*)malloc(sizeof(HeapNode));
    heapNode->vertex = vertex;
    heapNode->dist = dist;
    return heapNode;
}

// Create a min heap
MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->position = (int*)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (HeapNode**)malloc(capacity * sizeof(HeapNode*));
    return minHeap;
}

// Swap two heap nodes
void swapHeapNode(HeapNode** a, HeapNode** b) {
    HeapNode* temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify function
void heapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < minHeap->size && 
        minHeap->array[left]->dist < minHeap->array[smallest]->dist) {
        smallest = left;
    }
    
    if (right < minHeap->size && 
        minHeap->array[right]->dist < minHeap->array[smallest]->dist) {
        smallest = right;
    }
    
    if (smallest != idx) {
        HeapNode* smallestNode = minHeap->array[smallest];
        HeapNode* idxNode = minHeap->array[idx];
        minHeap->position[smallestNode->vertex] = idx;
        minHeap->position[idxNode->vertex] = smallest;
        
        swapHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        heapify(minHeap, smallest);
    }
}

// Check if heap is empty
bool isEmpty(MinHeap* minHeap) {
    return minHeap->size == 0;
}

// Extract minimum node from heap
HeapNode* extractMin(MinHeap* minHeap) {
    if (isEmpty(minHeap)) {
        return NULL;
    }
    
    HeapNode* root = minHeap->array[0];
    HeapNode* lastNode = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;
    minHeap->position[root->vertex] = minHeap->size - 1;
    minHeap->position[lastNode->vertex] = 0;
    
    minHeap->size--;
    heapify(minHeap, 0);
    
    return root;
}

// Decrease dist value in heap
void decreaseKey(MinHeap* minHeap, int vertex, int dist) {
    int i = minHeap->position[vertex];
    minHeap->array[i]->dist = dist;
    
    while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist) {
        minHeap->position[minHeap->array[i]->vertex] = (i - 1) / 2;
        minHeap->position[minHeap->array[(i - 1) / 2]->vertex] = i;
        swapHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Check if vertex is in min heap
bool isInMinHeap(MinHeap* minHeap, int vertex) {
    return minHeap->position[vertex] < minHeap->size;
}

// Dijkstra's Algorithm with Heap
void dijkstraHeap(Graph* graph, int source) {
    int V = graph->vertices;
    int dist[V];
    
    // Initialize distances
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }
    dist[source] = 0;
    
    // Create min heap
    MinHeap* minHeap = createMinHeap(V);
    
    // Initialize heap with all vertices
    for (int i = 0; i < V; i++) {
        minHeap->array[i] = createHeapNode(i, dist[i]);
        minHeap->position[i] = i;
    }
    minHeap->size = V;
    
    // Process vertices
    while (!isEmpty(minHeap)) {
        HeapNode* minNode = extractMin(minHeap);
        int u = minNode->vertex;
        
        // Traverse all neighbors of u
        Node* temp = graph->adjLists[u];
        while (temp != NULL) {
            int v = temp->vertex;
            int weight = temp->weight;
            
            // If v is in heap and distance can be improved
            if (isInMinHeap(minHeap, v) && 
                dist[u] != INT_MAX && 
                dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                decreaseKey(minHeap, v, dist[v]);
            }
            temp = temp->next;
        }
    }
    
    // Print results
    printf("Shortest distances from vertex %d:\n", source);
    printf("Vertex \t Distance\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1, 1);
    addEdge(graph, 0, 2, 4);
    addEdge(graph, 0, 3, 3);
    addEdge(graph, 1, 2, 2);
    addEdge(graph, 1, 4, 5);
    addEdge(graph, 2, 3, 6);
    addEdge(graph, 2, 4, 7);
    addEdge(graph, 3, 4, 8);
    
    dijkstraHeap(graph, 0);
    return 0;
}

Output:

Shortest distances from vertex 0:

Vertex   Distance
0        0
1        1
2        3
3        3
4        6

Complexity Analysis

Time Complexity

Space Complexity

• O(V) for the dist array and visited array.
• O(V + E) for the adjacency list representation.

Advantages of Dijkstra's Algorithm

1. Guaranteed Optimal: Finds the absolute shortest path for graphs with non-negative weights.
2. Versatile: Works on directed and undirected graphs.
3. Fast: With a binary heap, it runs in O((V + E) log V), which is efficient for most real-world graphs.
4. Widely Used: Standard algorithm in GPS navigation, network routing, and many other applications.

Disadvantages of Dijkstra's Algorithm

1. Fails with Negative Weights: It assumes that once a vertex is finalized, its distance cannot be improved. This is false with negative edges.
2. Not Suitable for Negative Cycles: If a negative cycle exists, the shortest path is undefined (can keep going around to get infinitely small distance).
3. Memory Intensive (Matrix): The adjacency matrix version uses O(V²) memory.

Real-World Applications of Dijkstra's Algorithm

Practice Questions

1. Given the following graph, find the shortest distances from vertex 0 using Dijkstra's algorithm. Edges: 0-1(4), 0-2(3), 0-3(1), 1-4(2), 1-5(5), 1-6(6)