BloodyStupidJohnson is an implementation of Johnson's Algorithm for All Pairs Shortest Paths.
It is considered to be faster in sparse graphs than FloydWarshall 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 ... n1 : Neighbours of n1
With neighbours specified as "TargetNodeIDwEdgeWeight"  Compile
 for compilation just unpack the zipFile 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_n1 ... n1 : distanceToNode_0 ... distanceToNode_n1
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 : 1w20 0w20
Which results in0 : 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/>.