pgRouting

Ticket #15 (closed bug report: fixed)

Opened 1 year ago

Last modified 1 year ago

No shortest path of edges with same source and target node

Reported by: daniel Assigned to: anton
Priority: major Milestone:
Component: A* Version: 1.0.0a
Keywords: Cc:

Description

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?

Attachments

ssp_parallel_nodes_bug.png (103.0 kB) - added by daniel on 06/14/07 23:23:36.
split_parallel_edges.sql (3.2 kB) - added by anton on 07/27/07 14:56:30.

Change History

06/14/07 23:23:36 changed by daniel

  • attachment ssp_parallel_nodes_bug.png added.

06/15/07 08:47:08 changed by anton

  • owner changed from somebody to anton.
  • status changed from new to assigned.

(in reply to: ↑ description ; follow-up: ↓ 3 ) 06/16/07 03:29:38 changed by 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.

(in reply to: ↑ 2 ) 06/16/07 04:24:37 changed by anton

  • priority changed from critical to major.

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.

07/27/07 14:56:30 changed by anton

  • attachment split_parallel_edges.sql added.

07/27/07 14:57:38 changed by anton

  • status changed from assigned to closed.
  • resolution set to fixed.

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