Shortest Path

[Lau]

How do I easily calculate the shortest path between two geographical spots on
a map?
The map is divided into zones. So I guess it is possible to use Dijkstra’s
Shortest Path algorithm, but it seems like a lot of work and I am sure that
it has been done many times before.
From (x,y) coordinates I need to place the user in a zone and find the
shortest path to all other zones.
Any suggestions are more than welcome. I would hate to reinvent the wheel!
Should I look at MS MapPoint or is that overkill?

--
--------------------

[Cowboy (Gregory A. Beamer) - MVP]

If you are talking which road to take, MapPoint web service is certainly an
option. I am fairly sure the expense of development time will outweigh the
expense of using MapPoint.

---

Gregory A. Beamer
MVP; MCP: +I, SE, SD, DBA

***************************
Think Outside the Box!
***************************

"Lau" wrote:

How do I easily calculate the shortest path between two geographical spots on
a map?
The map is divided into zones. So I guess it is possible to use Dijkstra’s
Shortest Path algorithm, but it seems like a lot of work and I am sure that
it has been done many times before.
From (x,y) coordinates I need to place the user in a zone and find the
shortest path to all other zones.
Any suggestions are more than welcome. I would hate to reinvent the wheel!
Should I look at MS MapPoint or is that overkill?

--
--------------------

[Lau]

MapPoint would be perfect, but we need to make our own maps. Actually all
maps are going to be building plans and that doesn’t appear to be possible in
MapPoint. Or?

[Kevin Yu [MSFT]]

Hi,

First of all, I would like to confirm my understanding of your issue. From
your description, I understand that you need to know what shortest path
algorithm MapPoint is using. If there is any misunderstanding, please feel
free to let me know.

I'm not quite sure about this. Since this question is something related to
MapPoint implementation, I suggest you to try asking in the following
newsgroups besides here.

microsoft.public.mappoint
microsoft.public.mappoint.webservice

HTH.

Kevin Yu
=======
"This posting is provided "AS IS" with no warranties, and confers no
rights."

[Lau]

Sorry, I don’t think I explained myself very good.

I’m not looking for MapPoints “shortest path algorithm�, but any algorithm
that can do the job. We need to make maps of theme parks, hotels, hospitals
i.e.
We idea is to find the shortest path from room A to room B. This is similar
to MapPoint, but it doesn’t seem to be possible to “make� your own maps in
MapPoint.

Therefore we are looking for a “shortest path algorithm� or preferably an
already implemented version.

[Colin Young]

What you need is graph theory. Here's the first hit from Google:
http://www.boost.org/libs/graph/doc/...ry_review.html

You could also look at this:
http://www.codeproject.com/cs/miscctrl/quickgraph.asp

It's an attempt to port the library in the first link to C#. I haven't tried
either libraries myself, but it should be a good start for you.

Colin

"Lau" <la*@newsgroup.nospam> wrote in message
news:34**********************************@microsof t.com...

Sorry, I don't think I explained myself very good.

I'm not looking for MapPoints "shortest path algorithm", but any algorithm
that can do the job. We need to make maps of theme parks, hotels, hospitals i.e.
We idea is to find the shortest path from room A to room B. This is similar to MapPoint, but it doesn't seem to be possible to "make" your own maps in
MapPoint.

Therefore we are looking for a "shortest path algorithm" or preferably an
already implemented version.

[Kevin Yu [MSFT]]

Hi,

There are many algorithms for us to get the shortest path on a graph.
Dijkstra and A* are two famous and commonly used algorithms. I think
searching through google will return many results. HTH.

Kevin Yu
=======
"This posting is provided "AS IS" with no warranties, and confers no
rights."