<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<meta name=ProgId content=Word.Document>
<meta name=Generator content="Microsoft Word 10">
<meta name=Originator content="Microsoft Word 10">
<link rel=File-List href="cid:filelist.xml@01C6759F.1F807540">
<link rel=Edit-Time-Data href="cid:editdata.mso@01C6759F.1F807540">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><o:SmartTagType
namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="date"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="time"/>
<!--[if gte mso 9]><xml>
<o:OfficeDocumentSettings>
<o:DoNotRelyOnCSS/>
</o:OfficeDocumentSettings>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:DocumentKind>DocumentEmail</w:DocumentKind>
<w:EnvelopeVis/>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;
mso-font-charset:0;
mso-generic-font-family:swiss;
mso-font-pitch:variable;
mso-font-signature:1627421319 -2147483648 8 0 66047 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;
text-underline:single;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Courier New";
mso-fareast-font-family:"Times New Roman";}
span.EmailStyle17
{mso-style-type:personal;
mso-style-noshow:yes;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;
font-family:Arial;
mso-ascii-font-family:Arial;
mso-hansi-font-family:Arial;
mso-bidi-font-family:Arial;
color:windowtext;}
span.EmailStyle18
{mso-style-type:personal-reply;
mso-style-noshow:yes;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;
font-family:Arial;
mso-ascii-font-family:Arial;
mso-hansi-font-family:Arial;
mso-bidi-font-family:Arial;
color:navy;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin:0in;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";}
</style>
<![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple style='tab-interval:.5in'>
<div class=Section1>
<p class=MsoPlainText><font size=2 face="Courier New"><span style='font-size:
10.0pt'>Thank Steve and Franck for the help.<o:p></o:p></span></font></p>
<p class=MsoPlainText><font size=2 face="Courier New"><span style='font-size:
10.0pt'>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.<o:p></o:p></span></font></p>
<p class=MsoPlainText><font size=2 color=navy face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoPlainText><font size=2 color=navy face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:navy'>Fay<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Tahoma><span
style='font-size:10.0pt;font-family:Tahoma'>-----Original Message-----<br>
<b><span style='font-weight:bold'>From:</span></b> zze-SIGALE PORTANERI F ext
RD-BIZZ-SOP [mailto:fportaneri.ext@rd.francetelecom.com] <br>
<b><span style='font-weight:bold'>Sent:</span></b> </span></font><st1:date
Month="5" Day="12" Year="2006"><font size=2 face=Tahoma><span style='font-size:
10.0pt;font-family:Tahoma'>Friday, May 12, 2006</span></font></st1:date><font
size=2 face=Tahoma><span style='font-size:10.0pt;font-family:Tahoma'> </span></font><st1:time
Hour="3" Minute="13"><font size=2 face=Tahoma><span style='font-size:10.0pt;
font-family:Tahoma'>3:13 AM</span></font></st1:time><font size=2 face=Tahoma><span
style='font-size:10.0pt;font-family:Tahoma'><br>
<b><span style='font-weight:bold'>To:</span></b> Fay Du;
cartoweb-users@lists.maptools.org; postgis-users@postgis.refractions.net<br>
<b><span style='font-weight:bold'>Subject:</span></b> RE: [Cartoweb-users]
Looking for single-destination (shortest path)program</span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>Hi Fay,</span></font><o:p></o:p></p>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'> <o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>In fact, dijkstra is
already calculating a graph from one point of the network (the source) to all
other points. See <a
href="http://www.nist.gov/dads/HTML/singleSourceShortestPath.html">http://www.nist.gov/dads/HTML/singleSourceShortestPath.html</a></span></font><o:p></o:p></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>An animation can be also
found at <a href="http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html">http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html</a></span></font><o:p></o:p></p>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'> <o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>The current pgdijkstra shortest_path()
fonction launches the full graph calculation and then retrieve the stack of
path only for the given target id.</span></font><o:p></o:p></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>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.</span></font><o:p></o:p></p>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'> <o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>However, one problem
could be that you have a directed network, and the shortest path from</span></font> <font
size=2 color=blue face=Arial><span style='font-size:10.0pt;font-family:Arial;
color:blue'>the client to the car could be different than the shortest path
from</span></font><font color=black><span style='color:black'> </span></font><font
size=2 color=blue face=Arial><span style='font-size:10.0pt;font-family:Arial;
color:blue'>the car to the client.... but may be it can help.</span></font><o:p></o:p></p>
<div>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'> <o:p></o:p></span></font></p>
</div>
<div>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>Regards</span></font><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal style='margin-left:.5in'><font size=2 color=blue face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:blue'>Franck</span></font><o:p></o:p></p>
</div>
<p class=MsoNormal style='margin-left:.5in'><font size=3 face="Times New Roman"><span
style='font-size:12.0pt'><o:p> </o:p></span></font></p>
<div class=MsoNormal align=center style='margin-left:.5in;text-align:center'><font
size=3 face="Times New Roman"><span lang=FR style='font-size:12.0pt;mso-ansi-language:
FR'>
<hr size=2 width="100%" align=center>
</span></font></div>
<p class=MsoNormal style='mso-margin-top-alt:0in;margin-right:0in;margin-bottom:
12.0pt;margin-left:.5in'><b><font size=2 face=Tahoma><span lang=FR
style='font-size:10.0pt;font-family:Tahoma;mso-ansi-language:FR;font-weight:
bold'>De :</span></font></b><font size=2 face=Tahoma><span lang=FR
style='font-size:10.0pt;font-family:Tahoma;mso-ansi-language:FR'> cartoweb-users-bounces@lists.maptools.org
[mailto:cartoweb-users-bounces@lists.maptools.org] <b><span style='font-weight:
bold'>De la part de</span></b> Fay Du<br>
<b><span style='font-weight:bold'>Envoyé :</span></b> jeudi 11 mai 2006
21:58<br>
<b><span style='font-weight:bold'>À :</span></b>
cartoweb-users@lists.maptools.org; postgis-users@postgis.refractions.net<br>
<b><span style='font-weight:bold'>Objet :</span></b> [Cartoweb-users]
Looking for single-destination (shortest path)program</span></font><span
lang=FR style='mso-ansi-language:FR'><o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'>Hi everyone:<o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'><span style='mso-spacerun:yes'>
</span>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?<o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'><span style='mso-spacerun:yes'>
</span>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.<o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'>Many, many thanks.<o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-left:.5in'><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'>Fay<o:p></o:p></span></font></p>
</div>
</body>
</html>