fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Floyd-Warshall
  4. //
  5. //  Created by Himanshu on 12/11/22.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <cmath>
  11. #include <climits>
  12. #define N 5
  13. using namespace std;
  14.  
  15. void printMatrix(int G[][N]) {
  16.  
  17.     for (int i=0; i<N; i++) {
  18.         for (int j=0; j<N; j++) {
  19.             if (G[i][j] == INT_MAX) {
  20.                 cout<<"INF ";
  21.             } else {
  22.                 cout<<G[i][j]<<" ";
  23.             }
  24.         }
  25.         cout<<endl;
  26.     }
  27. }
  28.  
  29. //n = number of nodes in graph
  30. void FloydWarshall (int P[][N]) {
  31.  
  32.     for (int k=0; k<N; k++) {
  33.  
  34.         for (int i=0; i<N; i++) {
  35.             for (int j=0; j<N; j++) {
  36.                 if (P[i][k] == INT_MAX || P[k][j] == INT_MAX) {
  37.                     P[i][j] = P[i][j];
  38.                 } else {
  39.                     P[i][j] = min(P[i][j], P[i][k] + P[k][j]);
  40.                 }
  41.             }
  42.         }
  43.  
  44.         cout<<endl<<"Path Matrix (P) after k = "<<(k+1)<<endl;
  45.         printMatrix (P);
  46.     }
  47.  
  48. }
  49.  
  50.  
  51. int main() {
  52.     int G[N][N] = {{0, 3, 8, INT_MAX, -4},
  53.                        {INT_MAX, 0, INT_MAX, 1, 7},
  54.                        {INT_MAX, 4, 0, INT_MAX, INT_MAX},
  55.                        {2, INT_MAX, -5, 0, INT_MAX},
  56.                        {INT_MAX, INT_MAX, INT_MAX, 6, 0}};
  57.  
  58.  
  59.     cout<<"Graph G (Adjacency Matrix):"<<endl;
  60.     printMatrix(G);
  61.  
  62.     cout<<endl<<"Floyd Warshall Algorithm:"<<endl;
  63.     FloydWarshall (G);
  64.  
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Graph G (Adjacency Matrix):
0 3 8 INF -4 
INF 0 INF 1 7 
INF 4 0 INF INF 
2 INF -5 0 INF 
INF INF INF 6 0 

Floyd Warshall Algorithm:

Path Matrix (P) after k = 1
0 3 8 INF -4 
INF 0 INF 1 7 
INF 4 0 INF INF 
2 5 -5 0 -2 
INF INF INF 6 0 

Path Matrix (P) after k = 2
0 3 8 4 -4 
INF 0 INF 1 7 
INF 4 0 5 11 
2 5 -5 0 -2 
INF INF INF 6 0 

Path Matrix (P) after k = 3
0 3 8 4 -4 
INF 0 INF 1 7 
INF 4 0 5 11 
2 -1 -5 0 -2 
INF INF INF 6 0 

Path Matrix (P) after k = 4
0 3 -1 4 -4 
3 0 -4 1 -1 
7 4 0 5 3 
2 -1 -5 0 -2 
8 5 1 6 0 

Path Matrix (P) after k = 5
0 1 -3 2 -4 
3 0 -4 1 -1 
7 4 0 5 3 
2 -1 -5 0 -2 
8 5 1 6 0
https://ideone.com/0VC9u8
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!