0

I have implemented the pgrouting Dijkstra one-to-many algorithm, and have noticed that the result is a table of every route together, with and edge value of -1 indicating the end of an individual route.

I am interested in selecting the cheapest route of all the routing results. By manually parsing and comparing the results via the agg_cost values, I have found that every single time, the first group of results (i.e. the rows up until the first -1 value is the) is the shortest path.

I'm wondering now if this is by design, if it is a consequence of Dijkstra's algorithm (or at least this implementation of it), or if it is just a coincidence given my relatively simply sample dataset.

Is it necessary to manually compare the routing results to find the shortest path, or will the first route in the group always be the shortest one?

1

According to the docs for pgr_KSP, yes, the first set of results is always the shortest path. Or more precisely, the set with the lowest path_id has the lowest cost.

The path_id field is defined as follows:

Path identifier. The ordering of the paths. For two paths i, j if i < j then agg_cost(i) <= agg_cost(j).

  • I am confused, this seems like a completely different algorithm, and one that does not allow for one-to-many routing, it just returns k routes for the same one-to-one routing problem. – wfgeo Apr 23 '17 at 11:06
  • Which algorithm were you using then? Edit your post to give the text of your query. – amball Apr 24 '17 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.