[go: up one dir, main page]
Scribd
Upload
52 views4 pages

WAP in C++ To Find The Shortest Path Between Source and Destination Using Warshall's Algorithm

This C++ program implements Warshall's algorithm to find the shortest path between any two vertices in a graph. It takes the number of vertices and edges as input, initializes a distance matrix to store shortest paths, updates the matrix by considering paths through intermediate vertices, and outputs the final distance matrix showing the shortest path between all pairs of vertices.

Uploaded by

सतीश पाण्डेय (पाण्डेय जी)
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
52 views4 pages

WAP in C++ To Find The Shortest Path Between Source and Destination Using Warshall's Algorithm

This C++ program implements Warshall's algorithm to find the shortest path between any two vertices in a graph. It takes the number of vertices and edges as input, initializes a distance matrix to store shortest paths, updates the matrix by considering paths through intermediate vertices, and outputs the final distance matrix showing the shortest path between all pairs of vertices.

Uploaded by

सतीश पाण्डेय (पाण्डेय जी)
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

2.

WAP in C++ to find the shortest path between


source and destination using Warshall’s Algorithm.
Input:

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

int main()
{
int i,j,k;
int n,e;
int s,d,w;

cout<<"Enter the number of vertices ";


cin>>n;

vector<vector<int> > distMat(n,vector<int>(n,INT_MAX));

for(i=0;i<n;i++)
{

distMat[i][i]=0;
}

cout<<"Enter the number of edges ";


cin>>e;
cout<<"Enter the src, dest and weight of each edge"<<endl;
for(i=0;i<e;i++)
{
cin>>s>>d>>w;

distMat[s-1][d-1]=w;
}

for(k=0;k<n;k++)
{

for(i=0;i<n;i++)
{

for(j=0;j<n;j++)
{
if(distMat[i][k]!=INT_MAX &&
distMat[k][j]!=INT_MAX &&
distMat[i][k]+distMat[k][j]<distMat[i][j])
{
distMat[i][j]=distMat[i][k]+distMat[k][j];
}

}
}
}

cout<<endl<<"The all pairs shortest distance matrix is "<<endl;

cout<<" ";

for(i=0;i<n;i++)
{
printf("%6d",i+1);
}

cout<<endl;

for(i=0;i<6*n;i++)
{
cout<<"_";
}

cout<<"_______"<<endl;

for(i=0;i<n;i++)
{
printf("%5d |",i+1);
for(j=0;j<n;j++)
{
if(distMat[i][j]==INT_MAX)
printf(" INF");
else
printf("%6d",distMat[i][j]);

cout<<endl;
}

return 0;
}

Ouput:

You might also like