Algorithm
//https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
#include<iostream>
using namespace std;
#define v 9
int minDist (int dist[], bool spset[]) {
int minIndex, min=INT_MAX;
for (int i=0; i<v; i++)
if (spset[i]== 0 && dist[i]<= min)
min=dist[i],minIndex= i;
return minIndex;
}
void dijkstra (int graph[][v], int s) {
bool spset[v]= {0};
int dist[v];
for (int i=0; i<v;i++)
dist[i]= INT_MAX;
dist[s]= 0;
for (int c=0; c<v-1; c++) {
int u= minDist(dist, spset);
spset[u]= 1;
for (int i=0;i<v; i++)
if (!spset[i] && graph[u][i]!=0 && dist[u]!= INT_MAX && dist[i]>dist[u]+graph[u][i])
dist[i]= dist[u]+graph[u][i];
}
for (int i=0;i<v;i++)
(dist[i]==INT_MAX)?cout<<i<< "\tInf\n":cout<<i<< "\t"<< dist[i]<<"\n";
}
int main() {
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, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
}