[pgrouting-dev] APSP Implementation
daniel at georepublic.de
Thu Dec 2 00:24:19 EST 2010
Let me make some proposal how the APSP function could look like.
(I mostly copy from Dijkstra:
CREATE OR REPLACE FUNCTION apsp(
RETURNS SETOF <???>
With *sql* as ...
SELECT id, source, target, cost FROM edge_table
... like for Dijkstra, and *n_ids/m_ids* as ...
SELECT id FROM edge_table
to select the relevant points for the n-m distance matrix.
With a select (instead of a list of ID's you can also select relevant points
by attribute, update timestamp or whatever.
I can also think of an APSP that calculates all distances from 1 point to n
points only. That's why I added n_ids/m_ids.
In that case you could update an existing distance matrix (that you stored
in some table for example) if only one or a few points changed.
One big question is what to return as a result.
And another question is if it will be possible to chose between Dijkstra,
A-Star or Shooting*.
2010/12/2 Daniel Kastl <daniel at georepublic.de>
>>> I think there will be both cases. DARP/TSP might only need the matrix at
>>> first. But when you got your optimized tour result you had to run again
>>> the shortest path search to retrieve a path, which causes two problems:
>>> * The network (conditions) might have changed if you run those path
>>> queries later.
>> I guess this assumes the you are getting live feed data for traffic or
>> something like that. What are you think here? Also be aware that the
>> algorithms can select any of equal distance alternatives and the later if
>> you single shortest path it might pick a different path, which may or may
>> not be problematic.
> I actually don't assume live feed data but the fact that pgRouting keeps
> the network in a database and it's possible to change attributes for
> example, that are part of your cost parameter, at any time. Or maybe road
> links become unavailable during a long APSP query.
> I think the library should ensure that when you make a query it reads the
> network data available at that time. If the query for processing a huge
> distance matrix takes one hour for example, but makes steadily new requests
> to the database, it could happen that some attributes change over time.
> Whether this is problematic for an application or not depends on the
> application. In most cases it probably isn't, that's true. But pgRouting
> isn't limited to road networks, so who knows what kind of applications will
> make use of it.
>> * It might be slower to later run single shortest path queries again
>> It would be interesting to enhance our single shortest path to be able to
>> extract multiple single shortest paths based on a single graph build. So
>> input might be something like
> This would be the same as k-Shortest Path, right?
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pgrouting-dev