6

I am running the shortest_path function but it will not return rows of lines to follow from source id to target id. Is there a specific way to digitise my dataset? Does pgrouting understand intersections between lines? I digitised my lines one by one connecting snapping them together.

To be a bit more clear, in my db i have a gid for every line, plus a source and target id for that line (plus the other columns). Shouldn't the shortest path function take me from a random source id to a random target id?

I hope my problem is clear but let me know if further explanation is needed :)

Thanks in advance. A

Improve this question
5
  • 1
    Start with a very simple case. The simplest test would be to route from a source to target on the same edge. If that doesn't work you might not have to correct columns. If it works test a target that is on a connecting edge. If that doesn't work your edges might not be correctedly conected, etc.
    – mrg
    Commented Jan 10, 2012 at 14:53
  • Sure, I tested what you suggested and it works with specific examples but not with others, so I guess I have wrongly connected vertices. So in my db there are sources and targets like this (gid:1,s:1,t:2),(gid:2,s:3,t:4)...In this case though, gid:1 is intersecting gid:2 but I guess a vertex is not properly created, eitherwise it would be picking it up..
    – Antony
    Commented Jan 10, 2012 at 15:08
  • 1
    Do you have a tool like QGIS? If so, load your network with that and put the layer in Edit mode. That way you see all verices and you can probably spot missing vertices. Otherwise select vertices that are only 1 time a source or target and make them visible to see where they lie. Dead ends are ok, but somewhere inside your network is probably wrong.
    – mrg
    Commented Jan 10, 2012 at 15:27
  • I can tell you what does not work for sure, if I digitise 10 parallel lines and then intersect all of them with one line, these intersections are not identified when I call assign_vertex_id. Now, if I digitise a line and then start a new line snaped at the end of the previous, this vertex is identified. But of course I want the first technique to work as well..So this probably means I have to digitise smaller lines and connect them using the end of the previous line as the beginning of the next? That would create lots of unnecessary data...but would work
    – Antony
    Commented Jan 10, 2012 at 16:04
  • You could run your old vector file through grass v.clean to get a version with split lines at every intersection.
    – underdark
    Commented Jan 10, 2012 at 17:08

2 Answers 2

Reset to default
4

Dijkstra's algorithm shortest path:

"the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities"

http://www.pgrouting.org/docs/1.x/dijkstra.html

enter image description here

Based on the Dijkstra's algorithm:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Improve this answer
2
  • 3
    This is indeed an answer to the title. Somehow i have a feeling that he kind of knows how it works but doesn't understand why it doesn't technically work for him.
    – mrg
    Commented Jan 10, 2012 at 15:31
  • 1
    Yes, I agree this is a straightforward answer to the title. My issue has to do with how the algorithm is identifying the verticies so that the dijkstra algorithm can work.
    – Antony
    Commented Jan 10, 2012 at 16:29
3

Shouldn't the shortest path function take me from a random source id to a random target id?

Yes, pgRouting's shortest_path can route from one vertex to another vertex (if there is a valid connection of course).

in my db i have a gid for every line, plus a source and target id for that line

How did you assign source and target id's? Did you use assign_vertex_id()?

It sounds like there is no valid connection between the start and end points you tested.

Does pgrouting understand intersections between lines?

No. There has to be a vertex at the intersection, otherwise it will not be recognized.

Update:

In this case though, gid:1 is intersecting gid:2 but I guess a vertex is not properly created

So you have two lines crossing each other? You need to split at the intersection (resulting in four lines) if you want to be able to turn on this intersection. Otherwise it's interpreted as an over-/under-pass.

Improve this answer
5
  • 1
    Hi, Yes, I used assign_vertex_id() and it was completed successfully. When I check my table \d <table> it looks like the example in the documentation with the vertices_tmp and vertices_tmp_seq.. When I created my lines in qgis, I was snapping them together so there are intersection that can be picked up. I also found this example, underdark.wordpress.com/2011/02/07/…, Should I try this instead? Although I do not understand what is going wrong..
    – Antony
    Commented Jan 10, 2012 at 14:38
  • Hmm, ok I am starting understanding how pgRouting works. So I can see some connections in my db. Some connections do exist but some others do not. But when I look at my lines, there is a path that can be followed to reach whichever I want through the intersections...
    – Antony
    Commented Jan 10, 2012 at 14:50
  • Sounds like snapping didn't work as well as you hoped it would. You can try the test @mrg suggested in his comment. Find the errors in your network topology and it should work.
    – underdark
    Commented Jan 10, 2012 at 15:06
  • Right, I ll try a smaller set and see how it goes. Lets hope its a snaping problem! Thanks for your time!
    – Antony
    Commented Jan 10, 2012 at 15:10
  • Yes, I just saw your update. I will try and work with smaller line segments. Thank you very much for your input.
    – Antony
    Commented Jan 10, 2012 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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