<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Am 20.05.2013 23:01, schrieb Peter K:<br>
</div>
<blockquote cite="mid:519A8F0D.4060202@yahoo.de" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<div class="moz-cite-prefix">Hi Chris,<br>
<br>
</div>
<blockquote
cite="mid:CAP=_uhRNBGF3GMpGbAwVEz75XO3VmuA=mc=-0Qg2EPfK=o7Wbw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div style="font-family:arial,sans-serif;font-size:13px">I'm
looking at using DijkstraOneToMany to get path costs (just
the sum of the edge weights, not the whole path) from a
single origin to all nodes closer than some fixed cost
limit.<br>
</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br>
</div>
<div style="font-family:arial,sans-serif;font-size:13px">I
know about findEndNode(), but am not sure if I need to walk
the graph of nodes myself, calling findEndNode() and
weight() on each node, or if there is a way to walk
exhaustively with only a limit as the termination point.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br>
</div>
<div style="font-family:arial,sans-serif;font-size:13px">Ideally,
I'd have something like findEndNodesAndCosts() that would
return a map of node ID to path cost for all nodes less than
the cost cutoff set with DijkstraOneToMany.limit(). What
would be the suggested implementation of this?<br>
</div>
</div>
</blockquote>
<br>
You already have all you need, I think. At the end of a call ala
findEndNode(node, -1) you need to iterate through the changed
nodes only:<br>
<br>
for(int i = 0; i < changedNodes.size(); i++) {<br>
int nodeIndex = changedNodes.get(i);<br>
// info: changedNodes could contain duplicates<br>
map.put(nodeIndex, weights[nodeIndex])<br>
}<br>
</blockquote>
<br>
hmmh, I think you'll have to remove all nodes from the priority
queue too. As for those nodes (except the first one) it is not
guaranteed to already have the minimum weight.<br>
You could do that either via iterating over the queue and then do
map.remove<br>
<br>
OR<br>
<br>
via introducing a new visitedNodes set and do somethink like this
pseudo code:<br>
// eg. with a TIntHashSet<br>
visitedNodes.forEach(-> int nodeIndex) {<br>
map.put(nodeIndex, weights[nodeIndex])<br>
}<br>
// but e.g. GHBitSetImpl would be the best in terms of memory usage:<br>
for each changedNodes but only if in visitedNodes -> int
nodeIndex {<br>
map.put(nodeIndex, weights[nodeIndex])<br>
}<br>
<br>
Regards,<br>
Peter.<br>
</body>
</html>