Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Graph::floyd_warshall()
- {
- this->is_reset = false;
- this->dist = this->graph;
- this->path = vector< vector<int> >(this->size, vector<int>(this->size, INF));
- for (int mid_node = 0; mid_node < this->size; mid_node++)
- {
- for (int st_node = 0; st_node < this->size; st_node++)
- {
- // No path from st_node -> mid_node, don't bother to try.
- if (this->dist[st_node][mid_node] == INF) { continue; }
- for (int end_node = 0; end_node < this->size; end_node++)
- {
- // No path from mid_node -> end_node, don't bother to try.
- if (this->dist[mid_node][end_node] == INF) { continue; }
- // Calculate the distance from st_node -> end_node when using mid_node
- int new_dist = this->dist[st_node][mid_node] + this->dist[mid_node][end_node];
- if (new_dist < this->dist[st_node][end_node])
- {
- this->dist[st_node][end_node] = new_dist; // Update distances
- }
- } // END end_node = 0 to size
- } // END st_node = 0 to size
- } // END mid_node = 0 to size
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement