All-pairs shortest paths is a standard pathfinding problem. This is a twist on that.
We are searching for paths on a directed graph. Graphs are defined by square matrices, for example
0 3 2.5 1 0 1 0 -1 0
M(r,c) = value in M at row r, column c is the cost to travel from node
r to node
c. The graph is in general asymmetric, costs may be negative, and
M(i,i)=0 for all
i. An edge with cost zero does not exist, i.e. treat zeros as infinities in the input.
Indexing from zero, the above graph can be visualised thus:
For a given valid, input matrix of any size output the matrix
MOUT(r,c)=cost of the shortest path from r to c and back to r
The twist is: you must make a return trip, without visiting any edges on the return trip which you used on the outward trip. That is,
M(c,r) are considered to be the same edge albeit with a cost which depends on the direction of travel.
For example, the shortest path from
0 -> 1 -> 0 may not include both the edges
Nor may you re-use an edge in the outward trip.
Each return trip is considered independently of the others. If you use
(0,1) in the path from
0 -> 1 -> 0 then you may use either
(1,0) in the path from
0 -> 2 -> 0.
Input is on stdin and output on stdout.
The input and output is a matrix with columns separated by a number of spaces, and rows separated by a single
Input entries are floating point numbers conforming to
/^-?[0-9]+(\.[0-9]*)?$/. Output entries are numbers of the same kind or
NaN or some equivalent symbol in the event that no return route exists between those nodes. A zero in the input matrix represents an infinite cost (non-existant edge) but zeroes in the output represent a cost-free journey.
Your program behaviour is undefined in the event that the input is not a finite real-valued square matrix.
Test against the following input matrices and post the results with your code.
0 6 -5 -2 9 -3 0 0 -4 5 7 2 0 -8 1 -6 3 4 0 -9 8 -3 -1 2 0
0 -0.3 2.4 -1 1 0 0.9 9.3 10 4 0 -2 8 -6 -7 0
0 1 0 2 0 0 3 1 4 0 0 2 0 1 0 1
Shortest code wins.