[pgrouting-dev] K-Shortest Path round-trip pattern question

[Stephen Woodbridge]

Nagase-san,

I answered this in the user list.

Basically there is not roundtrip support for any shortest path 
algorithm. Shorthest path is point to point and the shortest path from a 
point to itself is defined as zero.

-Steve

On 2/7/2015 3:23 AM, Ko Nagase wrote:
> Hi list,
>
> I am facing an issue about K-Shortest Path round-trip pattern.
>
> When I specified same source and target ids, then pgr_ksp results are
> invalid like this.
> ==========
> sampledata=# SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
>   FROM pgr_ksp(
>     'SELECT id, source, target, cost FROM edge_table',
>     1, 1, 4, false
>   );
>   seq | route | node |    edge     |         cost
> -----+-------+------+-------------+-----------------------
>     0 |     0 |    1 | -2147483648 | 1.79769313486232e+308
>     1 |     0 |    1 |          -1 |                     0
> (2 rows)
> ==========
>
> I think that the results should be as follows,
> because in my understanding, K-Shortest Path should support round-trip pattern.
> ==========
>   seq | route | node |    edge     |         cost
> -----+-------+------+-------------+-----------------------
>     0 |     0 |    1 |           1 |                     1
>     1 |     0 |    2 |           1 |                     1
>     2 |     0 |    1 |          -1 |                     0
>     3 |     1 |    1 |           1 |                     1
>     : |     : |    : |           : |                     :
> ==========
>
> But is my understanding wrong ?
> (Shouldn't K-Shortest Path support round-trip case ?)
>
> If my understanding is wrong, does someone know
> how to support round-trip case ?
>
>
> About above pgr_ksp issue, I created the ticket to here.
> [pgr_ksp returns invalid one route when source and target are same #287]
> https://github.com/pgRouting/pgrouting/issues/287
>
> Regards,
>