Dijkstra

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

int main(){
int cost[10][10],path[10][10],i,j,n,p,v,min,index=1;
int distance[10],row,column;

cout<<"Enter no. of nodes: ";
cin>>n;
cout<<"Enter cost matrix: \n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>cost[i][j];
}
}
printf("Enter the node you want to visit:");
cin>>v;
printf("Enter the path for the selected node:");
cin>>p;
cout<<"Enter the path matrix: \n";
for(i=1;i<=p;i++)
{
for(j=1;j<=n;j++)
{
cin>>path[i][j];
}
}

for(i=1;i<=p;i++){
distance[i]=0;
row=1;
for(j=1;j<=n;j++)
{
if(row!=v)
{
column=path[i][j+1];
distance[i]=distance[i]+cost[row][column];

}
row=column;

}

}
min=distance[1];
for(i=1;i<=p;i++)
{
if(distance[i]<=min)
{
min=distance[i];
index=i;
}
}
cout<<"The minimum distance is:";
cout<<min;
for(i=1;i<=n;i++){
if(path[index][i]!=0)
{
printf("-->%d",path[index][i]);
}
}

}
```

output:

```Enter no. of nodes: 5
Enter cost matrix:
0
4
0
8
0
4
0
3
0
0
0
3
0
4
0
8
0
4
0
7
0
0
0
7
0
Enter the node you want to visit:5
Enter the path for the selected node:2
Enter the path matrix: 1
2
3
4
5
1
4
5
0
0
The minimum distance is:15-->1-->4-->5```

Complexity:
O(E+V^2)

We are using here adjacency matrix list

It would be a great help, if you support by sharing :)
Author: zakilive