SHARE
TWEET

Floyd warshall

hadiuzzaman65 Oct 23rd, 2019 114 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define inf 999999
  3. #define neg -1
  4.  
  5.  
  6. using namespace std;
  7.  
  8. void printfun(int source, int des, vector< vector<int> >path)
  9. {
  10.     if(path[source][des]==-1)
  11.     {
  12.         cout<<"No path found."<<endl;
  13.         return;
  14.     }
  15.  
  16.     if(path[source][des]==source)
  17.         cout<<source<<" ";
  18.  
  19.     if(path[source][des]!=source)
  20.     {
  21.         printfun(source,path[source][des],path);
  22.         cout<<path[source][des]<<" ";
  23.     }
  24.  
  25.  
  26.  
  27.  
  28. }
  29.  
  30. int main()
  31. {
  32.     int node, edge;
  33.     cout<<"How many nodes: ";
  34.     cin>>node;
  35.     cout<< "How many edges: ";
  36.     cin>>edge;
  37.  
  38.     vector< vector<int> >distance(node,vector<int>(node));
  39.     vector< vector<int> >path(node,vector<int>(node));
  40.  
  41.     for(int i=0; i<node; i++)
  42.         for(int j=0; j<node; j++)
  43.             distance[i][j]=inf;
  44.  
  45.     for(int i=0; i<node; i++)
  46.         for(int j=0; j<node; j++)
  47.             path[i][j]=neg;
  48.  
  49.     for(int i=0; i<node; i++)
  50.         for(int j=0; j<node; j++)
  51.             if(i==j)
  52.             {
  53.                 distance[i][j]=0;
  54.                 path[i][j]=i;
  55.             }
  56.  
  57.     cout<<"Edge information (u,v,w)"<<endl;
  58.     for(int i=0; i<edge; i++)
  59.     {
  60.         int u,v,w;
  61.         cin>>u>>v>>w;
  62.  
  63.         distance[u][v]=w;
  64.         path[u][v]=u;
  65.     }
  66.  
  67.     for(int k=0; k<node; k++)
  68.         for(int i=0; i<node; i++)
  69.             for(int j=0; j<node; j++)
  70.                 if(distance[i][j]>distance[i][k]+distance[k][j])
  71.                 {
  72.                     distance[i][j]=distance[i][k]+distance[k][j];
  73.                     path[i][j]=k;
  74.                 }
  75.  
  76.     cout<<"distance matrix:"<<endl;
  77.     for(int i=0; i<node; i++)
  78.     {
  79.         for(int j=0; j<node; j++)
  80.         {
  81.             cout<<distance[i][j]<<" ";
  82.         }
  83.         cout<<endl;
  84.     }
  85.     cout<<endl;
  86.  
  87.     cout<<"path matrix:"<<endl;
  88.     for(int i=0; i<node; i++)
  89.     {
  90.         for(int j=0; j<node; j++)
  91.         {
  92.             cout<<path[i][j]<<" ";
  93.         }
  94.         cout<<endl;
  95.     }
  96.     cout<<endl;
  97.     cout<<"Source vertex: ";
  98.     int source, des;
  99.     cin>>source;
  100.     cout<< "Destination vertex: ";
  101.     cin>>des;
  102.  
  103.     cout<<"distance between "<<source<<" and "<<des<<" is : "<<distance[source][des]<<endl;
  104.     cout<<"Path : ";
  105.     printfun(source, des, path);
  106.     cout<<des<<endl;
  107.  
  108.     for(int i=0; i<node; i++)
  109.     {
  110.         for(int j=0; j<node; j++)
  111.         {
  112.             if(distance[i][j]<0 && i==j)
  113.             {
  114.                 cout<<"the graph has negative cycle"<<endl;
  115.                 return 0;
  116.             }
  117.             else
  118.             {
  119.                 cout<<"This Graph does not contain any negative cycle"<<endl;
  120.                 return 0;
  121.             }
  122.  
  123.         }
  124.     }
  125.  
  126.  
  127.  
  128. }
  129.  
  130.  
  131. /*
  132.  
  133. 4 6
  134.  
  135. 0 3 15
  136. 0 1 3
  137. 0 2 6
  138. 3 0 1
  139. 1 2 -2
  140. 2 3 2
  141.  
  142. 0 3
  143.  
  144. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top