Want more features on Pastebin? Sign Up, it's FREE!
Guest

Floyd-Warshall

By: a guest on Oct 25th, 2010  |  syntax: C++  |  size: 0.99 KB  |  views: 113  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. void Graph::floyd_warshall()
  2. {
  3.         this->is_reset = false;
  4.  
  5.         this->dist = this->graph;
  6.         this->path = vector< vector<int> >(this->size, vector<int>(this->size, INF));
  7.  
  8.         for (int mid_node = 0; mid_node < this->size; mid_node++)
  9.         {
  10.                 for (int st_node = 0; st_node < this->size; st_node++)
  11.                 {
  12.                         // No path from st_node -> mid_node, don't bother to try.
  13.                         if (this->dist[st_node][mid_node] == INF) { continue; }
  14.  
  15.                         for (int end_node = 0; end_node < this->size; end_node++)
  16.                         {
  17.                                 // No path from mid_node -> end_node, don't bother to try.
  18.                                 if (this->dist[mid_node][end_node] == INF) { continue; }
  19.  
  20.                                 // Calculate the distance from st_node -> end_node when using mid_node
  21.                                 int new_dist = this->dist[st_node][mid_node] + this->dist[mid_node][end_node];
  22.  
  23.                                 if (new_dist < this->dist[st_node][end_node])
  24.                                 {
  25.                                         this->dist[st_node][end_node] = new_dist;       // Update distances
  26.  
  27.                                 }
  28.                         }       // END end_node = 0 to size
  29.                 }       // END st_node = 0 to size
  30.         }       // END mid_node = 0 to size
  31. }
clone this paste RAW Paste Data