All-pairs shortest return paths without reusing edges

2

All-pairs shortest paths is a standard pathfinding problem. This is a twist on that.

Definitions

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

Goal

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.

Requirements

Test against the following input matrices and post the results with your code.

A:

 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

B:

 0  -0.3  2.4  -1
 1   0    0.9   9.3
10   4    0   -2 
 8  -6  -7  0

C:

0  1   0   2
0  0   3   1
4  0   0   2
0  1   0   1

Shortest code wins.

spraff

Posted 2016-12-05T15:37:40.297

Reputation: 881

Question was closed 2016-12-05T21:20:17.973

"*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? – Peter Taylor – 2016-12-05T16:30:43.293

Edited. No edge may be used twice within any one trip. – spraff – 2016-12-05T16:43:27.227

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. – mbomb007 – 2016-12-05T19:58:07.027

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? – spraff – 2016-12-06T09:30:05.850

No answers