Single Source Shortest Path

Category Archives: Single Source Shortest Path

Dijkstra

Posted on July 10, 2017 | Leave a comment

#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]);
    }
}

}

#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

Enter no. of nodes: 5

Enter cost matrix:

Enter the node you want to visit:5

Enter the path for the selected node:2

Enter the path matrix: 1

The minimum distance is:15-->1-->4-->5

Complexity:
O(E+V^2)

We are using here adjacency matrix list

Category Archives: Single Source Shortest Path

Bellman Ford

Dijkstra

Caution and Tips:

About Me & MyBlog

Recent Comments

Categories

My Facebook

Recent Posts

Archives

Category Archives: Single Source Shortest Path

Bellman Ford

Dijkstra

Caution and Tips:

About Me & MyBlog

Recent Comments

Categories

My Facebook

Recent Posts

Tags

Archives