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

Write 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:

enter image description here


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(r,c) and 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 (0,1) and (1,0).

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 (0,1) or (1,0) in the path from 0 -> 2 -> 0.

Input/Output Format

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 \n.

Input entries are floating point numbers conforming to /^-?[0-9]+(\.[0-9]*)?$/. Output entries are numbers of the same kind or Inf, Infinity, 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.

  • \$\begingroup\$ "you must make a return trip, without visiting any edges on the return trip which you used on the outward trip" So it's ok to visit the same edge twice on the outward trip? \$\endgroup\$ – Peter Taylor Dec 5 '16 at 16:30
  • \$\begingroup\$ Edited. No edge may be used twice within any one trip. \$\endgroup\$ – spraff Dec 5 '16 at 16:43
  • \$\begingroup\$ How is this truly scored? If it's scored by shortest code, then does it really matter how their program did on your test cases? Also, you should make it clearer how the matrix represents a graph. \$\endgroup\$ – mbomb007 Dec 5 '16 at 19:58
  • \$\begingroup\$ The program must produce correct output. Isn't that a given for all these contests? And I'm not sure what's unclear about the representation -- algebraic definition with an example and diagram, what else do you need? \$\endgroup\$ – spraff Dec 6 '16 at 9:30