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

Ko Nagase nagase at georepublic.co.jp
Sat Feb 7 07:33:12 PST 2015


Hi Stephen,

Thanks for your answer.

2015-02-08 0:09 GMT+09:00 Stephen Woodbridge <woodbri at swoodbridge.com>:
> 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.

Okay.
Thanks for clarification.

Regards,

> 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,
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev



-- 
Ko Nagase (長瀬 興)
Georepublic Japan
mail: nagase at georepublic.co.jp
web: http://georepublic.co.jp


More information about the pgrouting-dev mailing list