Keith O'Hara kthohr
ashleyholman
/ johnson.cpp
Created
October 2, 2013 13:01
This code implements Johnson's algorithm to solve the "all pairs shortest path" problem, ie. given an input graph with general edge weights (can be negative) with no negative cycles, find the shortest (u, w) path for all pairs of vertices (u, w). If the input graph has any negative cycles, the program will report this and halt (since there is no…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <fstream> | |
| #include <vector> | |
| #include <climits> | |
| #include <exception> | |
| #include <set> | |
| using namespace std; | |
| struct Edge { |