If, like me, you neglected to check and see if pgRouting (the pathfinding library for PostGIS) handles parallel edges in its default shortest path query, then you’ve likely found out that it doesn’t. You can tell that something is wrong when the same least cost path query produces different results, this is because the query is pulling the first edge it finds, which may not be the same edge query after query, and also may not be the least expensive edge. It’s a relatively easy fix, but I figure I’ll point out how to handle it here.
Remember, when you’re pulling a shortest path it looks something like this:
SELECT
*
FROM
shortest_path(
'SELECT
gid as id,
source::integer,
target::integer,
cost::double precision
FROM
edge_table',
true,
false)
It’s how you select your table of edges that allows you to handle parallel edges in your shortest_path subquery. You can fashion a SELECT DISTINCT ON query that orders the edges by cost so that you ensure the Dijkstra distance algorithm is only looking at the least expensive available edges:
SELECT
*
FROM
shortest_path(
'SELECT DISTINCT ON (source, target)
gid as id,
source::integer,
target::integer,
cost::double precision
FROM
edge_table
ORDER BY
source,
target,
cost
',
true,
false)
Since ASC (ascending) is the default order, then this will only give one edge per source-target pair and it will be the least expensive edge. If you were looking for the least cost path but you had different edges representing, say, best and worst case scenarios, and you wanted to do a path for the worst-case, then I suppose you could ORDER BY source, target, cost DESC.
Now imagine doing this where you’re evaluating the edge cost based on different vehicle types and different months of the year and different possible costs (in the case of the Roman transportation network, we can determine the shortest, cheapest or fastest path, which is not necessarily the same path between two sites). In that case, you simply include the same expression that you use to determine your cost in the ORDER BY function. I’ll post the full PostGIS function when we release the network–it’s rather complicated–but I figured I’d post this little bit in case anyone else runs into the same problem that I did.