No shortest path of edges with same source and target node

[daniel]

Node based shortest path algorithms (Dijkstra, A*) cannot distinguish between two edges, that have same source and same target (parallel edges). Randomly one of those edges will be selected for the route (see attached screenshot).

To be able to use node based algorithms, two nodes may not have the same source and target. How can this be taken into account? How to verify (and correct) those edges, when creating the network topology?

[jonnio]

Replying to daniel:

Node based shortest path algorithms (Dijkstra, A*) cannot distinguish between two edges, that have same source and same target (parallel edges). Randomly one of those edges will be selected for the route (see attached screenshot). To be able to use node based algorithms, two nodes may not have the same source and target. How can this be taken into account? How to verify (and correct) those edges, when creating the network topology?

Even if there is more than one path from node to node, there can only be one 'lowest cost' method. There might need to be a procedure to clean up your dataset and remove all but the lowest cost edge.

[anton]

Replying to jonnio:

Replying to daniel:

Node based shortest path algorithms (Dijkstra, A*) cannot distinguish between two edges, that have same source and same target (parallel edges). Randomly one of those edges will be selected for the route (see attached screenshot). To be able to use node based algorithms, two nodes may not have the same source and target. How can this be taken into account? How to verify (and correct) those edges, when creating the network topology?

Even if there is more than one path from node to node, there can only be one 'lowest cost' method. There might need to be a procedure to clean up your dataset and remove all but the lowest cost edge.

Yes, I agree - there shouldn't be parallel edges. But we just cannot remove any edge - what if somebody will want to calculate a shortest path from/to those edge? I think we need to split them somehow at the topology creation stage.

[anton]

See split_parallel_edges.sql (attached) for a sample function which splits parallel edges.