Dijikstra's Algorithm for Shortest Path

 

Dijkstra’s Algorithm — Concept

Purpose:
To find the shortest path from a source vertex to all other vertices in a weighted graph (with non-negative edge weights).

Key Idea:
We repeatedly pick the vertex with the minimum tentative distance (using a priority queue or min-heap), and then update (relax) the distances to its neighboring vertices.

---

⚙️ Data Structures Used

1. Array / Min-heap → to store and find the vertex with the minimum distance.

2. Adjacency Matrix or Adjacency List → to represent the graph.

3. Visited Set → to keep track of vertices whose shortest distance is finalized.

---

🧠 Algorithm Steps 

1. Initialize the distance of all vertices to ∞, and the source vertex to 0.

2. Mark all vertices as unvisited.

3. Choose the unvisited vertex with the smallest distance (call it u).

4. For each neighbor v of u, check if the path through u gives a shorter distance:

   if dist[u] + weight(u, v) < dist[v]:
       dist[v] = dist[u] + weight(u, v)
   

5. Mark u as visited.

6. Repeat until all vertices are visited.

---

🧮 Example

Let’s take a weighted graph with 6 vertices (A, B, C, D, E,F):

Edge	Weight
A–B	4
A–C	2
B–C	5
B–D	10
C–E	3
E–D	4
D–F	11

E-F           11

We will find shortest paths from A.

---

Step 1: Initialization

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

---

Step 2: Start with A

From A:

• B = min(∞, 0 + 4) = 4

• C = min(∞, 0 + 2) = 2

Vertex	Distance	Previous
A	0	—
B	4	A
C	2	A
D	∞	—
E	∞	—
F	∞	—

Mark A as visited.

---

Step 3: Pick the next vertex with smallest distance → C (2)

From C:

• E = min(∞, 2 + 3) = 5

• B = min(4, 2 + 5) = 4 (no change)

Vertex	Distance	Previous
A	0	—
B	4	A
C	2	A
D	∞	—
E	5	C
F	∞	—

Mark C as visited.

---

Step 4: Next smallest → B (4)

From B:

• D = min(∞, 4 + 10) = 14

• C = already visited

Vertex	Distance	Previous
A	0	—
B	4	A
C	2	A
D	14	B
E	5	C
F	∞	—

Mark B as visited.

---

Step 5: Next → E (5)

From E:

• D = min(14, 5 + 4) = 9

• F = min(∞, 5 + 11) = 16

Vertex	Distance	Previous
A	0	—
B	4	A
C	2	A
D	9	E
E	5	C
F	16	E

Mark E as visited.

---

Step 6: Next smallest → D (9)

From D:

• F = min(16, 9 + 11) = 16 (no change)

Mark D as visited.
Finally mark F as visited.

---

✅ Final Shortest Distances from A

Vertex	Distance	Path
A	0	A
B	4	A → B
C	2	A → C
D	9	A → C → E → D
E	5	A → C → E
F	16	A → C → E → F

Shortest Path to All vertices

---

🧩 Summary

• Dijkstra’s algorithm ensures the shortest path from the source to every other vertex.

• It is a greedy algorithm because it makes the locally optimal choice (minimum distance) at each step.

• Time complexity:

• With adjacency matrix: O(V²)

• With min-heap + adjacency list: O((V + E) log V)

Simple Implementation- Dijikstra's Algorithm

#include <stdio.h>

#define INF 9999

#define MAX 10

int main() {

    int n, i, j, start;

    int cost[MAX][MAX], dist[MAX], visited[MAX], count, minDist, nextNode;

    printf("Enter the number of vertices: ");

    scanf("%d", &n);

    printf("Enter the cost adjacency matrix (use 9999 for no edge):\n");

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            scanf("%d", &cost[i][j]);

        }

    }

    printf("Enter the starting vertex (0 to %d): ", n - 1);

    scanf("%d", &start);

    // Step 1: Initialize distances and visited array

    for (i = 0; i < n; i++) {

        dist[i] = cost[start][i];

        visited[i] = 0;

    }

    dist[start] = 0;

    visited[start] = 1;

    count = 1;

    // Step 2: Repeat until all vertices are visited

    while (count < n - 1) {

        minDist = INF;

        // Step 3: Find the unvisited vertex with the smallest distance

        for (i = 0; i < n; i++) {

            if (dist[i] < minDist && !visited[i]) {

                minDist = dist[i];

                nextNode = i;

            }

        }

        visited[nextNode] = 1;

        // Step 4: Update distances of neighbors of nextNode

        for (i = 0; i < n; i++) {

            if (!visited[i]) {

                if (minDist + cost[nextNode][i] < dist[i]) {

                    dist[i] = minDist + cost[nextNode][i];

                }

            }

        }

        count++;

    }

    // Step 5: Print the shortest distances

    printf("\nShortest distances from vertex %d:\n", start);

    for (i = 0; i < n; i++) {

        if (i != start)

            printf("To vertex %d = %d\n", i, dist[i]);

    }

    return 0;

}

Enter the number of vertices: 6

Enter the cost adjacency matrix (use 9999 for no edge):

9999         4         2         9999     9999     9999

4             9999     5         10         9999     9999

2             5         9999     9999     3            9999

9999     10         9999     9999     4            11

9999     9999     3             4         9999     11

9999     9999     9999     11         11         9999

Enter the starting vertex (0 to 5): 0

Shortest distances from vertex 0:

To vertex 1 = 4

To vertex 2 = 2

To vertex 3 = 9

To vertex 4 = 5

To vertex 5 = 16