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

Leave a Reply

Your email address will not be published.