bloodyStupidJohnson

Implementation of Johnson's Algorithm for All Pairs Shortest Paths

BloodyStupidJohnson is an implementation of Johnson's Algorithm for All Pairs Shortest Paths. It is considered to be faster in sparse graphs than Floyd-Warshall and it works on graphs with negative edge weight (as long as there are no negative cycles, but then the shortest distance is not defined anyway)

This program was written in collaboration by Markus Pargmann and Alexander Weinhold

Note about the name:
The name "BloodyStupidJohnson" is not meant to be an insult to Johnson, it's rather a pun on the commonness of Terry Pratchett addiction among computer scientists. Consult wikipedia for further help...

The program could probably use some cleaning up...
DOWNLOAD


Prerequisites
- g++ Compiler
Graph file
The actual graph has to be specified as follows:
# comment lines*
n = NumberOfNodes
m = NumberOfEdges
0 : Neighbours of 0
...
n-1 : Neighbours of n-1
With neighbours specified as "TargetNodeIDwEdgeWeight"
Compile
for compilation just unpack the zip-File and type
g++ -o johnson *.cpp
Run
./johnson graphFile
With graphFile being the name of the text file you specified your graph in.
Output
The output looks as follows:
0 : distanceToNode_0 ... distanceToNode_n-1
...
n-1 : distanceToNode_0 ... distanceToNode_n-1
So basically a distance matrix. Unless there are negative cycles in the graph - in this case you will see an error message.
Example
Example of a small graph

# first comment
# second comment
n = 3
m = 5
0 : 1w100 2w50
1 : 2w40
2 : 1w-20 0w20
Which results in
0 : 0 30 50
1 : 60 0 40
2 : 20 -20 0
License:
 BloodyStupidJohnson is an implementation of Johnson's algorithm
 for the All Pairs Shortest Paths problem.
 Copyright (C) 2010 Markus Pargmann and Alexander Weinhold

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation, version 2 of the License.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.