Scribd
Upload
9 views3 pages

Data Algorithm

The document describes how to implement Warshall's algorithm to find the shortest paths between all pairs of vertices in a weighted directed graph. It provides code snippets in C and C++ that take a graph as input, apply the Floyd-Warshall algorithm to generate a path matrix, and output the results.

Uploaded by

Soumya Ranjan Behera
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
9 views3 pages

Data Algorithm

The document describes how to implement Warshall's algorithm to find the shortest paths between all pairs of vertices in a weighted directed graph. It provides code snippets in C and C++ that take a graph as input, apply the Floyd-Warshall algorithm to generate a path matrix, and output the results.

Uploaded by

Soumya Ranjan Behera
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/ 3

1.

Implement Warshall’s algorithm to generate path matrix for a directed


graph.
#include <stdio.h> void

printMatrix(int matrix[][nV]); void

floydWarshall(int graph[][nV])

int matrix[nV][nV], i, j, k; for (i = 0; i < nV;

i++) for (j = 0; j < nV; j++) matrix[i][j] =

graph[i][j]; for (k = 0; k < nV; k++) { for (i

= 0; i < nV; i++) { for (j = 0; j < nV; j++) { if

(matrix[i][k] + matrix[k][j] < matrix[i][j])

matrix[i][j] = matrix[i][k] + matrix[k][j];

printMatrix(matrix);

void printMatrix(int matrix[][nV]) {

for (int i = 0; i < nV; i++) { for (int j

= 0; j < nV; j++) { if (matrix[i][j] ==

INF) printf("%4s", "INF") else

printf("%4d", matrix[i][j]);

printf("\n");

int main() { int graph[nV][nV] =

{{0, 3, INF, 5},

{2, 0, INF, 4},


{INF, 1, 0, INF}, {INF,

INF, 2, 0}};

floydWarshall(graph);

2.Implement Floyd Warshall’s algorithm to generate all pairs Shortest


paths for a directed graph for a directed weighted graph.
#include<iostream>

using namespace std;

int main(){

int m,i,j,k; cout<<"Number of Vertics will be: "; cin>>m; long

A[m][m],P[m][m]; cout<<"Enter the Adjacency Matrix Below in

"<<m<<"x"<<m<<" size:"<<endl; for(i=0;i<m;i++){ for(j=0;j<m;j++){

cin>>A[i][j]; if(A[i][j]!=0)P[i][j]=1; else P[i][j]=0;

}
cout<<endl;

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

for(j=0;j<m;j++){

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

P[i][j]=P[i][j]+P[i][k]*P[k][j];

if(P[i][j]!=0)P[i][j]=1;

cout<<"Path Matrix :"<<endl;

for(i=0;i<m;i++){ for(j=0;j<m;j++)

cout<<P[i][j]<<" ";

cout<<endl;

cout<<endl;

return 0;

You might also like