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...
- 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-1With neighbours specified as "TargetNodeIDwEdgeWeight"
- for compilation just unpack the zip-File and type
g++ -o johnson *.cpp
./johnson graphFileWith graphFile being the name of the text file you specified your graph in.
The output looks as follows:
0 : distanceToNode_0 ... distanceToNode_n-1 ... n-1 : distanceToNode_0 ... distanceToNode_n-1So basically a distance matrix. Unless there are negative cycles in the graph - in this case you will see an error message.
Example of a small graph
# first comment # second comment n = 3 m = 5 0 : 1w100 2w50 1 : 2w40 2 : 1w-20 0w20Which results in
0 : 0 30 50 1 : 60 0 40 2 : 20 -20 0
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/>.