Dijkstra's Algorithm for Shortest Path Problem

Impementation of Dijkstra's Algorithm in C .

The shortest path problem is a fundamental concept in data structures and algorithms, particularly within graph theory. In essence, it involves finding the path with the minimum cost or distance between two vertices in a graph

Introduction

The shortest path problem seeks to identify the most efficient route between two points in a network. This network can be represented as a graph, where vertices represent locations, and edges represent the connections between them. Each edge is typically assigned a weight, which could represent distance, cost, time, or any other relevant metric.

Key Concepts

Graph: A data structure consisting of vertices (nodes) and edges that connect these vertices. Graphs can be directed (edges have a direction) or undirected (edges are bidirectional).
Vertices: Represent locations or nodes in the graph .
Edges: Represent the connections or paths between vertices. Edges can be labeled or unlabeled.
Weight: A value assigned to each edge representing the “cost” of traversing that edge.
Shortest Path: The path between two vertices in a graph that minimizes the sum of the weights of the edges along the path.

Dijkstra’s Algorithm:

Purpose: Dijkstra’s Algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. It can also be used to find the shortest path from a single node to a single destination node by stopping the process once the shortest path has been determined.
How it Works: The algorithm maintains a set of visited vertices and keeps track of the shortest distance between each vertex and the source vertex. It iteratively updates these distances as shorter paths are discovered.
Key Idea: Dijkstra’s algorithm calculates the shortest distance between two places.
Limitation: Note that Dijkstra’s algorithm does not work for graphs with negative edge weight

Algorithm :

Goal: Find the shortest paths from a single source vertex to all other vertices in a weighted graph where all edge weights are non-negative.

Input:

G = (V, E): A graph with vertices V and edges E.
w(u, v): Weight function for edge (u, v), representing the cost of travelling from vertex u to vertex v.
s: The source vertex.

Output:

d[v]: The shortest distance from the source vertex s to vertex v for all v in V.

Algorithm:

Initialization:
- For all vertices v in V:
  - d[v] = infty (set initial distance to infinity)
  - previous[v] = null (the predecessor of v in the shortest path)
- d[s] = 0 (distance from source to itself is zero)
- Q = V (create a set Q containing all the vertices in the graph)
Main Loop:
- While Q is not empty:
  - u = vertex in Q with minimum d[u] (find the vertex u in Q with the smallest distance d[u])
  - Remove u from Q
  - For each neighbor v of u:
    - alt = d[u] + w(u, v) (calculate the distance to v through u)
    - If alt < d[v]: (if a shorter path to v is found)
      - d[v] = alt (update the distance to v)
      - previous[v] = u (mark u as the predecessor of v)
Return:
- d (the array of shortest distances from s to each vertex in V)
- previous (allows you to reconstruct the shortest path from s to any vertex)

Assignment 6. Set A a) SPPU:

Write a C program for the implementation of Dijkstra’s shortest path algorithm for finding shortest path from a gien source vertex using adjacency cost matrix.

#include <limits.h>

#define MAX_VERTICES 100

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

// Function to print the distance array
void printSolution(int dist[], int V) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) {
            printf("%d \t Unreachable\n", i);
        } else {
            printf("%d \t %d\n", i, dist[i]);
        }
    }
}

// Dijkstra's algorithm
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int V) {
    int dist[V];         // Distance array
    int visited[V];      // Visited array

    // Initialize distances and visited array
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0; // Distance from source to itself is 0

    // Main loop
    for (int count = 0; count < V - 1; count++) {
        // Find the vertex with the minimum distance
        int u = minDistance(dist, visited, V);
        visited[u] = 1; // Mark the vertex as processed

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

    // Print the distance array
    printSolution(dist, V);
}

int main() {
    int V, E;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);

    int graph[MAX_VERTICES][MAX_VERTICES] = {0};

    printf("Enter the number of edges: ");
    scanf("%d", &E);

    printf("Enter the edges (source destination weight):\n");
    for (int i = 0; i < E; i++) {
        int src, dest, weight;
        scanf("%d %d %d", &src, &dest, &weight);
        graph[src][dest] = weight; // Directed graph (only one direction)
    }

    int src;
    printf("Enter the source vertex: ");
    scanf("%d", &src);

    dijkstra(graph, src, V);

    return 0;
}

Input Graph: ( Assuming you are using the graph in your Lab Book )

Vertices: 0, 1, 2, 3, 4
Edges:
0 -> 1: 10
0 -> 3: 5
1 -> 2: 1
1 -> 3: 2
2 -> 4: 4
3 -> 1: 3
3 -> 2: 9
3 -> 4: 2
4 -> 0: 7
4 -> 2: 6
Source Vertex: 0

Expected Output :

Vertex Distance from Source
0 0
1 8
2 9
3 5
4 7

Vertex 0:
- Distance: 0
- Explanation: This is the source vertex. The distance from the source to itself is always 0.
Vertex 1:
- Distance: 8
- Explanation: The shortest path from 0 to 1 is 0 -> 3 -> 1 with a total weight of 5 + 3 = 8.
Vertex 2:
- Distance: 9
- Explanation: The shortest path from 0 to 2 is 0 -> 3 -> 1 -> 2 with a total weight of 5 + 3 + 1 = 9.
Vertex 3:
- Distance: 5
- Explanation: The shortest path from 0 to 3 is 0 -> 3 with a total weight of 5.
Vertex 4:
- Distance: 7
- Explanation: The shortest path from 0 to 4 is 0 -> 3 -> 4 with a total weight of 5 + 2 = 7.