Advertisement
keverman

Floyd-Warshall algorithm

Feb 9th, 2020
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #define ll long long
  2. #define fi first
  3. #define se second
  4. int V;
  5. using _edge = pair<int, ll>;
  6. vector<vector<_edge>> edges;
  7.  
  8. vector<vector<ll>> FloydWarshall()
  9. {
  10.     vector<vector<ll>> dist(V, vector<ll>(V, LLONG_MAX));
  11.  
  12.     for(int u = 0; u < V; u++)
  13.     {
  14.         dist[u][u] = 0;
  15.         for(_edge e : edges[u])
  16.             dist[u][e.fi] = e.se;
  17.     }
  18.  
  19.     for(int i = 0; i < V; i++)
  20.         for(int u = 0; u < V; u++)
  21.             for(int v = 0; v < V; v++)
  22.                 if(dist[u][i] != LLONG_MAX && dist[i][v] != LLONG_MAX)
  23.                     dist[u][v] = min(dist[u][v], dist[u][i] + dist[i][v]);
  24.  
  25.     return dist;
  26. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement