[Cartoweb-users] Looking for single-destination (shortest path)program

[Fay Du]

Thank Steve and Franck for the help.
As Franck said, my network is directed, the path from client site to a
car site could be different with the path from car site to the client
site. For example, in a one way street, you can easily to go form one
point to another by following the traffic direction. But if you want go
back to you start point, you have to go to other streets to make a loop
back. The 2 paths are different.
 
Fay
 
 
-----Original Message-----
From: zze-SIGALE PORTANERI F ext RD-BIZZ-SOP
[mailto:fportaneri.ext at rd.francetelecom.com] 
Sent: Friday, May 12, 2006 3:13 AM
To: Fay Du; cartoweb-users at lists.maptools.org;
postgis-users at postgis.refractions.net
Subject: RE: [Cartoweb-users] Looking for single-destination (shortest
path)program
 
Hi Fay,
 
In fact, dijkstra is already calculating a graph from one point of the
network (the source) to all other points. See
http://www.nist.gov/dads/HTML/singleSourceShortestPath.html
An animation can be also found at
http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html
 
The current pgdijkstra shortest_path() fonction launches the full graph
calculation and then retrieve the stack of path only for the given
target id.
It can be very simple (i.e. with one call to dijksta) to get the nearest
car from the client by using the client as the source point. It needs
some extension to the current dijkstra contrib code to pass one source
id (client) and an array of target (cars) to the current shortest_path
function: When the graph is complete, you just need to choose the target
from the list which gives the smaller cost.
 
However, one problem could be that you have a directed network, and the
shortest path from the client to the car could be different than the
shortest path from the car to the client.... but may be it can help.
 
Regards
Franck
 
  _____  

De : cartoweb-users-bounces at lists.maptools.org
[mailto:cartoweb-users-bounces at lists.maptools.org] De la part de Fay Du
Envoyé : jeudi 11 mai 2006 21:58
À : cartoweb-users at lists.maptools.org;
postgis-users at postgis.refractions.net
Objet : [Cartoweb-users] Looking for single-destination (shortest
path)program
Hi everyone:
 
   I am trying to use pgDijkstra in my project. pgDijkstra calls boost
library which provides single-source shortest function. My network is a
street network. The graph is directed. My typical scenario is, there is
one client calls dispatch center and there are many cars (for example,
100 cars) are available all over the network. I want to find the closet
car and dispatch it to the client. It is a single-destination problem.
Does anyone know if there is an existing single-destination program
exists available for my project? Or the explanation of the
single-destination algorithm?
   I know I can call pgDijkstra multiple times to get the answer. The
performance of the solution is not good. Our goal is to calculate
shortest paths of 100 cars to the same destination in less than a
second. Calling pgDijkstra 100 times takes much, much more time than our
goal.
 
Many, many thanks.
Fay
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.maptools.org/pipermail/cartoweb-users/attachments/20060512/3ad6ab10/attachment-0001.html