Dijkstra's Algorithm

Dijkstra's Algorithm

Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a source vertex to all other vertices in a weighted, directed graph. The graph can have positive weights but cannot have negative weight edges. Dijkstra's algorithm guarantees finding the shortest path for graphs with non-negative weights.

Key Properties:

• Greedy Choice: At each step, the algorithm selects the vertex with the smallest known distance and updates the distances to its neighbors.
• Efficiency: It is widely used in scenarios like GPS navigation, networking, and route optimization where you need to find the shortest path in a graph.

Steps of Dijkstra's Algorithm:

1. Initialize:

   • Set the distance to the source vertex as 0 and the distance to all other vertices as infinity (∞).
   • Set all vertices as unvisited.
   • Create a priority queue (or min-heap) to efficiently select the vertex with the smallest distance.

2. Set of Visited Vertices:

   • While there are unvisited vertices:
     • Choose the vertex u with the smallest tentative distance from the priority queue (or the one with the smallest distance among unvisited vertices).
     • For each neighbor v of u, if the distance to v via u is smaller than the current known distance to v, update the distance to v.
     • Mark u as visited.

3. Repeat:

   • Continue this process until all vertices are visited or the queue is empty.
   • The distance array now contains the shortest distances from the source vertex to all other vertices.

4. Termination:

   • Once all vertices are visited, the algorithm terminates. The distance array provides the shortest path from the source to all vertices.

Example:

Consider the following weighted graph with 5 vertices labeled 0, 1, 2, 3, and 4.

     10      30
  (0)----(1)------(2)
   |       |        |
   50     10       60
   |       |        |
  (3)----(4)-------(5)

Vertices: {0, 1, 2, 3, 4}
Edges and their weights:

• (0, 1, 10)
• (0, 3, 50)
• (1, 2, 30)
• (1, 4, 10)
• (2, 5, 60)
• (3, 4, 10)

Let’s find the shortest path from vertex 0 to all other vertices using Dijkstra's algorithm.

Steps in Dijkstra's Algorithm:

1. Initialization:

   • Distance from the source (vertex 0):
     dist[0] = 0, dist[1] = ∞, dist[2] = ∞, dist[3] = ∞, dist[4] = ∞
   • Set of visited vertices: visited = {}.
   • Priority Queue (min-heap): [(0, 0)], where (distance, vertex).

2. Step 1: Start with vertex 0:

   • Vertex 0 has the smallest tentative distance of 0, so we process it.
   • Update the neighbors of vertex 0:
     • For edge (0, 1, 10), update dist[1] = 10.
     • For edge (0, 3, 50), update dist[3] = 50.
   • New distances: dist[0] = 0, dist[1] = 10, dist[2] = ∞, dist[3] = 50, dist[4] = ∞.
   • Add vertex 1 and vertex 3 to the priority queue: [(10, 1), (50, 3)].

3. Step 2: Process vertex 1 (next smallest distance):

   • Update the neighbors of vertex 1:
     • For edge (1, 2, 30), update dist[2] = 40 (since dist[1] + 30 = 10 + 30 = 40).
     • For edge (1, 4, 10), update dist[4] = 20 (since dist[1] + 10 = 10 + 10 = 20).
   • New distances: dist[0] = 0, dist[1] = 10, dist[2] = 40, dist[3] = 50, dist[4] = 20.
   • Add vertex 2 and vertex 4 to the priority queue: [(20, 4), (50, 3), (40, 2)].

4. Step 3: Process vertex 4 (next smallest distance):

   • Update the neighbors of vertex 4:
     • For edge (4, 3, 10), update dist[3] = 30 (since dist[4] + 10 = 20 + 10 = 30).
   • New distances: dist[0] = 0, dist[1] = 10, dist[2] = 40, dist[3] = 30, dist[4] = 20.
   • Add vertex 3 to the priority queue: [(30, 3), (40, 2), (50, 3)].

5. Step 4: Process vertex 3 (next smallest distance):

   • There are no new updates because vertex 3’s neighbors have already been processed.
   • New distances: dist[0] = 0, dist[1] = 10, dist[2] = 40, dist[3] = 30, dist[4] = 20.

6. Step 5: Process vertex 2 (next smallest distance):

   • No new updates because all of vertex 2’s neighbors have already been processed.

7. Termination:

   • All vertices have been processed, and the algorithm terminates. The shortest paths from vertex 0 are:
     • dist[0] = 0
     • dist[1] = 10
     • dist[2] = 40
     • dist[3] = 30
     • dist[4] = 20

Final Shortest Distances:

• Vertex 0: 0
• Vertex 1: 10
• Vertex 2: 40
• Vertex 3: 30
• Vertex 4: 20

C++ Code for Dijkstra's Algorithm:

Here’s an implementation of Dijkstra's Algorithm using a priority queue (min-heap) in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Define the structure for a graph edge (destination, weight)
typedef pair<int, int> Edge; // first = destination, second = weight

// Dijkstra's Algorithm
void dijkstra(int V, const vector<vector<Edge>>& adjList, int source) {
    // Distance array to store the shortest path from source to each vertex
    vector<int> dist(V, INT_MAX);
    dist[source] = 0;

    // Min-heap priority queue to store {distance, vertex}
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    pq.push({0, source});  // Starting with the source vertex

    while (!pq.empty()) {
        // Get the vertex with the smallest distance
        int u = pq.top().second;
        pq.pop();

        // Process all the adjacent vertices of u
        for (const Edge& edge : adjList[u]) {
            int v = edge.first;
            int weight = edge.second;

            // If the path through u is shorter, update the distance to v
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // Print the shortest distances from the source vertex
    cout << "Shortest distances from vertex " << source << ":\n";
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << endl;
    }
}

int main() {
    int V = 6;  // Number of vertices
    vector<vector<Edge>> adjList(V);

    // Add edges to the adjacency list (u, v, weight)
    adjList[0].push_back({1, 10});
    adjList[0].push_back({3, 50});
    adjList[1].push_back({2, 30});
    adjList[1].push_back({4, 10});
    adjList[2].push_back({5, 60});
    adjList[3].push_back({4, 10});

    int source = 0;  // Source vertex
    dijkstra(V, adjList, source);