dijkstra

Detailed Explanation of Dijkstra's Algorithm

Dijkstra's Algorithm

Definition

Dijkstra's algorithm is a greedy algorithm used to compute the single-source shortest paths in a weighted graph. Given a graph and a starting vertex, the algorithm finds the shortest path from the starting vertex to all other vertices.

Steps

1. Initialization: Set the distance of the starting vertex to 0 and the distances of all other vertices to infinity.
2. Select the vertex with the smallest distance among the unprocessed vertices and mark it as processed.
3. Update the distances of the adjacent vertices of the selected vertex.
4. Repeat steps 2 and 3 until all vertices have been processed.

Code Implementation (C)

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

#define V 9 // Number of vertices

// Find vertex with minimum distance
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min) {
            min = dist[v], minIndex = v;
        }
    }

    return minIndex;
}

// Print shortest path tree
void printSolution(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 src) {
    int dist[V];
    bool sptSet[V];
    
    // Initialize
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX, sptSet[i] = false;
    }

    // Starting vertex
    dist[src] = 0;

    // V-1 iterations
    for (int count = 0; count < V - 1; count++) {
        // Find the nearest vertex
        int u = minDistance(dist, sptSet);
        // Add to shortest path set
        sptSet[u] = true;

        // Update distances of adjacent vertices
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    dijkstra(graph, 0);

    return 0;
}

3. Time and Space Complexity Analysis

Dijkstra's Algorithm

• Time Complexity: $O(V^2)$ when using an adjacency matrix, or $O(E \log V)$ when using an adjacency list with a priority queue.
• Space Complexity: $O(V)$, primarily used for storing the shortest-path tree and visit markers.

Comparative Study: Prim's Algorithm

Dijkstra's and Prim's algorithms are highly similar, differing by almost a single line of code, making them ideal for comparative study.

Prim's algorithm is a greedy algorithm that works by gradual expansion. It starts from a single vertex and progressively adds the minimum-weight edge until all vertices are included in the tree.

Steps:

1. Choose a starting vertex and add it to the minimum spanning tree.
2. Repeat the following steps until the minimum spanning tree includes all vertices:
   • Among all edges connecting included and non-included vertices, select the edge with the minimum weight. (Here, it is the edge with the minimum weight from a non-included vertex to the set of already-included vertices, not the edge weight to the starting vertex -- this is where it differs from Dijkstra's algorithm.)
   • Add the selected edge and its corresponding vertex to the minimum spanning tree.

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

#define V 5

// Among all edges connecting included and non-included vertices, select the edge with minimum weight
// This finds the minimum weight edge by updating edges connected to vertices already in the MST set
int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}


// Print MST
void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V]) {

    // graph[V][V] stores edge weight values

    int parent[V]; // Parent nodes
    int key[V]; // Current key values for MST
    int mstSet[V]; // Whether vertex is included in MST

    // Initialize
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = 0;

    key[0] = 0;
    parent[0] = -1;
    
    // Prim's algorithm
    for (int count = 0; count < V - 1; count++) {
        // Find vertex with minimum key value
        int u = minKey(key, mstSet);

        // Add to MST set
        mstSet[u] = 1;

        // Update key values of adjacent vertices
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0}};
    primMST(graph);
    return 0;
}