Coders Packet

Dijkstra's Algorithm in C++

By Dhruv Prakash Raipure

A C++ packet which performs Dijkstra Algorithm. Helps find the most optimal path (least cost path) in a graph (uni-directional or bi-directional) from a source point to rest of the points.

The packet helps in finding the most optimal path from a given source point to all other mentioned points in the graph. The points and the overall graph can be visualized as a road map of cities or other relevant structures.


The packet uses the standard library in C++ , bits/stdc++.h.
The Dijkstra Algorithm is a greedy approach algorithm that decides the optimal path by checking the next point which is adjacent to the current point with the least distance. To keep a track of points that are adjacent to each other we use a 2D matrix called as Weighted Adjacency Matrix. It is a square matrix with dimensions equal to the number of points in the graph. Each intersection point (eg A12 denotes the cost of the edge between 1 and 2 in a bi-directional matrix and cost from 1 to 2 in a uni-directional matrix). Value 99999 denotes infinity (not directly reachable or adjacent).


The packet has two functions.
1.
Function min. Helps to find out the next nearest point from the current running point.
2.
Function remove. A queue is maintained in the code which consists of all the points in the graph. The min function tells which point to remove from the queue to move next.

The packet asks for 3 inputs.
1. The number of nodes/points in the graph
2. The weighted adjacency matrix (example image given below)
3. The source point from which the optimal distances till every other point needs to be calculated.


The packet outputs optimal paths from the source to all other points in the graph with the minimum cost required through those paths.

Sample Input/Output

Sample Graph

Graph

The adjacency matrix description is stated above.

Sample Input-Output 1

Dijkstra1   

Sample Input-Output 2

Dijkstra2

The first line input number of vertices/nodes. The second line is the 6x6 adjacency matrix as 6 points mentioned in the number of vertices input. The source vertex for the first sample is point 3 which outputs the corresponding output and for the second sample, it's 1 which yields the corresponding output.

 

Download Complete Code

Comments

No comments yet