C Implementation of Dijkstra's Shortest Path Algorithm This document provides a detailed analysis of a standard C implementation of Dijkstra's algorithm, a classic algorithm used to find the shortest paths from a single source node to all other nodes in a weighted graph.
Project Overview The program takes a graph represented by an adjacency matrix and a source vertex as input. It then calculates the shortest distance from the source vertex to every other vertex in the graph. The implementation assumes a graph with non-negative edge weights, which is a requirement for Dijkstra's algorithm.
Code Structure The code is organized into a single C file containing several functions that work together to execute the algorithm. The primary data structures are integer arrays used to store distances and track visited nodes.
Function-by-Function Breakdown int minDistance(int dist[], bool sptSet[], int V) This is a crucial helper function used within the main algorithm loop.
Purpose: To find the vertex with the minimum distance value from the set of vertices not yet included in the shortest path tree (sptSet).
Parameters:
int dist[]: An array containing the current shortest distance estimates from the source to each vertex.
bool sptSet[]: A boolean array where sptSet[i] is true if vertex i is already included in the shortest path tree (i.e., its final shortest distance is known).
int V: The total number of vertices in the graph.
Logic:
Initializes a minimum value to infinity (INT_MAX) and an index for the minimum value vertex.
Loops through all vertices from 0 to V-1.
Inside the loop, it checks if a vertex has not been visited yet (sptSet[v] == false) and if its currently known distance (dist[v]) is less than the current minimum.
If both conditions are true, it updates the minimum value and the index.
Returns: The index of the unvisited vertex with the smallest distance.
void printSolution(int dist[], int V) This is a simple utility function for displaying the final results.
Purpose: To print the calculated shortest distances from the source to each vertex in a clear, readable format.
Parameters:
int dist[]: The final array containing the shortest distances.
int V: The total number of vertices.
Logic:
Prints a header message.
Loops from 0 to V-1, printing each vertex index and its corresponding shortest distance from the source.
void dijkstra(int graph[V][V], int src, int V) This is the core function where Dijkstra's algorithm is implemented.
Purpose: To compute the shortest paths from a given source vertex (src) to all other vertices.
Parameters:
int graph[V][V]: The adjacency matrix representation of the graph, where graph[i][j] is the weight of the edge from vertex i to j. A value of 0 means no direct edge.
int src: The index of the source vertex (from 0 to V-1).
int V: The total number of vertices.
Logic:
Initialization:
Creates the dist[V] array. It sets the source vertex's distance to 0 and all other distances to infinity (INT_MAX).
Creates the sptSet[V] boolean array and initializes all its values to false, indicating that no vertex has been processed yet.
Main Loop:
The loop runs V-1 times, as in each iteration, one vertex's final shortest path is determined.
Step A: Calls the minDistance() function to pick the unvisited vertex (u) with the smallest current distance.
Step B: Marks the picked vertex u as processed by setting sptSet[u] = true.
Step C: Updates the distance values of the adjacent vertices of the picked vertex u. It iterates through all other vertices (v) and updates dist[v] only if all of the following are true:
v has not been visited yet (sptSet[v] is false).
There is an edge from u to v (graph[u][v] is not 0).
The total weight of the path from src to v through u is smaller than the current value of dist[v].
Finalization: After the loop finishes, it calls printSolution() to display the results.
int main() The driver function to set up the graph and start the algorithm.
Purpose: To define the graph structure, specify the source, and invoke the dijkstra function.
Logic:
Initializes an adjacency matrix graph with hardcoded edge weights.
Sets the source vertex (e.g., 0).
Calls dijkstra(graph, 0, V) to run the algorithm.
Returns: 0 on successful execution.