<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML xmlns="http://www.w3.org/TR/REC-html40" xmlns:o =
"urn:schemas-microsoft-com:office:office" xmlns:w =
"urn:schemas-microsoft-com:office:word"><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content=Word.Document name=ProgId>
<META content="MSHTML 6.00.2900.2873" name=GENERATOR>
<META content="Microsoft Word 10" name=Originator><LINK
href="cid:filelist.xml@01C67513.A8BF8530" rel=File-List><!--[if gte mso 9]><xml>
<o:OfficeDocumentSettings>
<o:DoNotRelyOnCSS/>
</o:OfficeDocumentSettings>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:SpellingState>Clean</w:SpellingState>
<w:GrammarState>Clean</w:GrammarState>
<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]-->
<STYLE>@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; }
P.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Times New Roman"; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
LI.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Times New Roman"; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
DIV.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0in 0in 0pt; FONT-FAMILY: "Times New Roman"; mso-style-parent: ""; mso-pagination: widow-orphan; mso-fareast-font-family: "Times New Roman"
}
A:link {
COLOR: blue; TEXT-DECORATION: underline; text-underline: single
}
SPAN.MsoHyperlink {
COLOR: blue; TEXT-DECORATION: underline; text-underline: single
}
A:visited {
COLOR: purple; TEXT-DECORATION: underline; text-underline: single
}
SPAN.MsoHyperlinkFollowed {
COLOR: purple; TEXT-DECORATION: underline; text-underline: single
}
SPAN.EmailStyle17 {
COLOR: windowtext; FONT-FAMILY: Arial; mso-style-type: personal-compose; mso-style-noshow: yes; mso-ansi-font-size: 10.0pt; mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Arial; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial
}
SPAN.SpellE {
mso-style-name: ""; mso-spl-e: yes
}
SPAN.GramE {
mso-style-name: ""; mso-gram-e: yes
}
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 style="tab-interval: .5in" vLink=purple link=blue>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>Hi Fay,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>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></FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>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></FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>The current pgdijkstra shortest_path() fonction launches
the full graph calculation and then retrieve the stack of path only for the
given target id.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>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.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=821344706-12052006><FONT face=Arial
color=#0000ff size=2>However, one problem could be that you have a directed
network, and the shortest path from</FONT> <FONT face=Arial color=#0000ff
size=2>the client to the car could be different than the shortest path from<FONT
face="Times New Roman" color=#000000 size=3> </FONT><FONT face=Arial
color=#0000ff size=2>the car to the client.... but may be it can
help.</FONT></FONT></SPAN></DIV>
<DIV><SPAN class=821344706-12052006><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=821344706-12052006><FONT face=Arial color=#0000ff
size=2>Regards</FONT></SPAN></DIV>
<DIV><SPAN class=821344706-12052006><FONT face=Arial color=#0000ff
size=2>Franck</FONT></SPAN></DIV>
<DIV dir=ltr align=left><BR></DIV>
<DIV class=OutlookMessageHeader lang=fr dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>De :</B>
cartoweb-users-bounces@lists.maptools.org
[mailto:cartoweb-users-bounces@lists.maptools.org] <B>De la part de</B> Fay
Du<BR><B>Envoyé :</B> jeudi 11 mai 2006 21:58<BR><B>À :</B>
cartoweb-users@lists.maptools.org;
postgis-users@postgis.refractions.net<BR><B>Objet :</B> [Cartoweb-users]
Looking for single-destination (shortest path)program<BR></FONT><BR></DIV>
<DIV></DIV>
<DIV class=Section1>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Hi
everyone:<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><SPAN
style="mso-spacerun: yes"> </SPAN>I am trying to use <SPAN
class=SpellE>pgDijkstra</SPAN> in my project. <SPAN class=SpellE><SPAN
class=GramE>pgDijkstra</SPAN></SPAN> 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? <SPAN class=GramE>Or
the explanation of the single-destination
algorithm?</SPAN><o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><SPAN
style="mso-spacerun: yes"> </SPAN>I know I can call <SPAN
class=SpellE>pgDijkstra</SPAN> 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 <SPAN
class=SpellE>pgDijkstra</SPAN> 100 times takes much, much more time than our
goal.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Many, many
thanks.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Fay<o:p></o:p></SPAN></FONT></P></DIV></BODY></HTML>