Implementation of Dijkstra Algorithm to find the shortest path

[kishan-25]

Dijkstra's Algorithm Implementation Overview

Overview Dijkstra's algorithm is a well-known graph search algorithm designed to find the shortest path from a source node to all other nodes in a weighted graph. This implementation utilizes an adjacency matrix representation.

Key Components

Graph Representation

• The graph is represented as a 2D array (graph[53][53]), where graph[i][j] indicates the weight of the edge between nodes i and j. A weight of 0 signifies no edge.

Distance Array

• An array (distance[53]) stores the shortest distance from the source node to each node in the graph. All distances are initialized to infinity (INT_MAX), except for the source node, which is set to 0.

Stat Array

• A boolean array (stat[53]) tracks which nodes have been finalized (i.e., the shortest path to them has been found). Initially, all nodes are marked as unvisited (false).

Finding the Minimum Distance Node

• The mindistance(int distance[], bool stat[]) function identifies the unvisited node with the smallest distance value, essential for selecting the next node to process.

  Algorithm Steps

Initialization

• The dijkstra function initializes the distance and stat arrays. The distance to the source node is set to 0, while all other distances are set to infinity.

Main Loop

• The algorithm processes all nodes (from 0 to 52) in a loop:
  • Calls mindistance to find the unvisited node with the smallest distance.
  • Marks this node as visited by updating the corresponding stat entry to true.

Relaxation

• For the current node m, the algorithm checks each of its neighbors (nodes i):
  • If node i is unvisited and there is an edge from m to i (i.e., graph[m][i] is not 0), it checks if the distance to i can be minimized by going through m.
  • If a shorter path is found, it updates distance[i].

Output

• After processing all nodes, the algorithm outputs the minimum distances from the source to each station.

Example Usage

• In the main function, a hardcoded adjacency matrix represents a specific graph (e.g., stations like Gandhi Nagar, Karond, etc.).
• The user is prompted to select a source station to calculate the shortest paths from this station to all others.

Conclusion This implementation effectively demonstrates Dijkstra's algorithm for finding the shortest paths in a graph. The choice of an adjacency matrix allows for straightforward graph representation and manipulation. The algorithm's time complexity is (O(V^2)), where (V) is the number of vertices, making it suitable for the graph size (53 vertices).

[kishan-25]

I hope this message finds you well! I’d like to request that this issue be assigned to me under the label of Hacktoberfest2024. Thank you!

[Ayu-hack]

Already exists. Bring something new n unique buddy. More repos are available for pull requests, and they’re part of Hacktoberfest 2024. Feel free to tag me in your Hacktoberfest certificate or badges LinkedIn post! 😄

👉 Follow my GitHub and connect with me on LinkedIn! ⭐ Star these repos to stay updated for next year’s Hacktoberfest!