i am doing a project which is similar to the nokia navigator or google map.... what i want to know is how to represent the whole city in form of a graph and even if i figure that out how to find all the possible paths between two given vertices?? does any of u have any idea about any standard algorithm that can do that????

Quote: Original post by oyeluckyoye
what i want to know is how to represent the whole city in form of a graph

Presumably the simplest here would be to place a graph vertex at every intersection, and connect the vertices with edges running along the road segments, where the edge weight is the length of that road segment.

Quote: and even if i figure that out how to find all the possible paths between two given vertices??

Finding all paths between 2 vertices is not a very well defined problem. Is backtracking allowed? Are loops allowed?

However, if you want the shortest path between the two vertices, Djikstra's algorithm is what you need (although other algorithms will work too).

creating a graph for the whole city in a manner told in the above reply is of course the simplest but not practical at all.... i want something that could b dynamic enough.... it should b like a generic function which can produce graphs for any input given to it ...

can somebody help with that....

and yes djikistra's algo can find the shortest path between two vertices but not all the possible paths and yes backtracking and loops are allowed...

Quote: Original post by swiftcoder
However, if you want the shortest path between the two vertices, Djikstra's algorithm is what you need (although other algorithms will work too).

Also, the A* algorithm is an extension of Dijkstra's algorithm, where additional information about the structure of the search space is used to pre-emptively cull during the exploration many paths that have a lower chance of being the shortest. In the case of road navigation, such information exists an can be quite helpful.

Quote: Original post by oyeluckyoye
i want something that could b dynamic enough.... it should b like a generic function which can produce graphs for any input given to it ...

If not a graph, what would your map be represented as when your program receives it?

Quote: and yes djikistra's algo can find the shortest path between two vertices but not all the possible paths and yes backtracking and loops are allowed...

If you allow backtracking and loops, the number of paths is infinite by definition. Depending on what you need them for, different ways of obtaining them can be discussed (there are algorithms to compute the infinite list of paths sorted by length, for instance).

Quote: Original post by swiftcoder

Quote: Original post by oyeluckyoye
what i want to know is how to represent the whole city in form of a graph

Presumably the simplest here would be to place a graph vertex at every intersection, and connect the vertices with edges running along the road segments, where the edge weight is the length of that road segment.[...]

For something like google maps, you want to use the time it takes to travel a road as the weight, not just the length. Thus, you'd use something like 'Length / Speed Limit * Traffic Factor + Signal Factor' where traffic factor is 1.0 for roads that are not at all congested and some greater value if traffic regularly reduces the average speed below the speed limit, and signal factor can be used to adjust for the time expected waiting on traffic lights, stop signs, etc.

For a serious google-like map, you don't want to get all possible paths (even without loops and backtracking), unless you own a super computer with megatons of storage.

Just consider the simplest example, where you have a fixed number n of nodes. The number of possible paths is n! = n * (n-1) * (n-2) ... * 1 (known as the faculty function). For just 5 nodes it is 120, for 6 it is 720, for 10 it is 3628800, for 25 it is already something like 15,511,210,043,330,985,984,000,000 (according to the calculator).

Looking at the title of the thread, I was all prepared to hop in here and answer "A*"... but the this "all possible paths" thing came up. I'm left shaking my head and wondering why you would even want that information.

I've always wondered about this: In game development we always talk about graph-search algorithms like A*, but in optimal control theory we talk about dynamic programming, and nobody ever seems to link the two.

If you poke around in the dynamic programming page's links a bit you'll come across "all pairs shortest path" algorithms that might be useful. The Floyd-Warshall algorithm is one example, and Wikipedia has links to implementations in various languages. I didn't look at all of them but the C implementation looks pretty straight forward. The Boost Graph Library has this and a few other similar algorithms for C++ if you're familiar with using those.

Regarding the creation of the graph, though, that's a tough problem. What do you mean by "a generic function which can produce graphs for any input given to it?" This makes sense if you want to generate a random map or you have a set of maps already in the format you need, but not if you're looking to generate a graph based on real streets. You're either going to have to bite the bullet and make it manually, develop some image processing routines to create a graph from a map image, or find someone that will do or has done it for you. For the last option, maybe you could look into using OpenStreetMap data, though of course that will take time to learn as well. If there is a simple solution to this, I'd also like to hear it.