code

#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum
// distance value, from the set of vertices not yet included
// in shortest path tree

int minDistance(int dist[], bool sptSet[], unordered_map<int, string> mp)
{
// Initialize min value
int min = INT_MAX, min_index;
for (int i = 0; i < V; i++)
if (sptSet[i] == false && dist[i] <= min)
min = dist[i], min_index = i;
return min_index;
}

// Function to print shortest path from source to j using
// parent array
void printPath(int parent[], int j, unordered_map<int, string> mp)
{
// Base Case : If j is source
if (parent[j] == -1)
return;
printPath(parent, parent[j], mp);
cout << "->"<< mp[j] ;
}

// A utility function to print the constructed distance
// array
void printSolution(int dist[], int n, int parent[], unordered_map<int, string> mp)
{
int src, dest;
cout<<"Enter the source:";
cin>>src;
cout<<"Enter the destination:";
cin>>dest;
if(src>=n|| dest>=n || src<0 || dest<0)
{
cout<<"Invalid input!";
return;
}
system("clear");
cout<<"\n\n--------Shortest Path Discovered!----------\n-------------------------------------------\n";
cout<<"Source: "<<mp[src]<<endl<<"Destination: "<<mp[dest]<<"\nDistance: "<<dist[dest]<<"\nPath:
"<<mp[src];
printPath(parent, dest, mp);
}

// Function that implements Dijkstra's single source
// shortest path algorithm for a graph represented using
// adjacency matrix representation
void dijkstra(int graph[V][V], int src, unordered_map<int, string> mp)
{
// The output array. dist[i] will hold the shortest
// distance from src to i
int dist[V];

// sptSet[i] will true if vertex i is included / in
// shortest path tree or shortest distance from src to i
// is finalized
bool sptSet[V] = { false };

// Parent array to store shortest path tree
int parent[V] = { -1 };

// Initialize all distances as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of
// vertices not yet processed. u is always equal to
// src in first iteration.
int u = minDistance(dist, sptSet, mp);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet,
// there is an edge from u to v, and total
// weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v]
&& dist[u] + graph[u][v] < dist[v]) {
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
// print the constructed distance array
printSolution(dist, V, parent, mp);
}

// Driver Code
int main()
{
// Let us create the example graph discussed above
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, 14, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
unordered_map<int, string> mp;
mp[8] = "shiva temple";
mp[7] = "arch-gate";
mp[6] = "biotech";
mp[5] = "SRM hospital";
mp[4] = "potheri";
mp[3] = "kc";
mp[1] = "tech-park";
mp[0] = "ub";

for(auto x:mp)
{
cout<<x.first<<" "<<x.second<<endl;
}
dijkstra(graph, 0,mp);
cout<<"\n-------------------------------------------\n";
int a;
cout<<"\n\n\n1. Explore more paths.\n2. Exit.\n\nPlease input your selection: ";
cin>>a;
if(a==1)

dijkstra(graph, 0,mp);
if(a==2)
return 0;
else
cout<<"\nInvalid input!\n";
return 0;
}