|
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----- 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 : [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] De la part de Fay Du 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 |
_______________________________________________ Cartoweb-users mailing list [email protected] http://lists.maptools.org/mailman/listinfo/cartoweb-users
