Revision 35157 trunk/extensions/extGraph/src/org/gvsig/graph/solvers/ShortestPathSolverDijkstra.java
ShortestPathSolverDijkstra.java | ||
---|---|---|
41 | 41 |
package org.gvsig.graph.solvers; |
42 | 42 |
|
43 | 43 |
import java.util.ArrayList; |
44 |
import java.util.PriorityQueue; |
|
44 | 45 |
|
45 | 46 |
import org.gvsig.exceptions.BaseException; |
46 | 47 |
import org.gvsig.graph.core.AbstractNetSolver; |
... | ... | |
153 | 154 |
node.setStatus(GvNode.statNowInList); |
154 | 155 |
bestCost = Double.MAX_VALUE; |
155 | 156 |
// Priority Queue |
156 |
FibHeap pq = new FibHeap(graph.numVertices());
|
|
157 |
pq.insert(node, 0);
|
|
157 |
PriorityQueue<GvNode> pq = new PriorityQueue<GvNode>();
|
|
158 |
pq.add(node);
|
|
158 | 159 |
|
159 | 160 |
// Mientras que la lista de candidatosSTL no est? vac?a, procesamos |
160 | 161 |
// Nodos |
161 | 162 |
|
162 |
while ((!bExit) && (!pq.empty())) {
|
|
163 |
while ((!bExit) && (!pq.isEmpty())) {
|
|
163 | 164 |
// Buscamos el nodo con m?nimo coste |
164 | 165 |
// node = (GvNode) candidatos.get(0); |
165 | 166 |
// bestNode = node; |
... | ... | |
174 | 175 |
// |
175 | 176 |
// |
176 | 177 |
// node = bestNode; |
177 |
node = (GvNode) pq.extract_min(); // get the lowest-weightSum Vertex 'u',
|
|
178 |
node = pq.poll(); // get the lowest-weightSum Vertex 'u',
|
|
178 | 179 |
// Borramos el mejor nodo de la lista de candidatosSTL |
179 | 180 |
node.setStatus(GvNode.statWasInList); |
180 | 181 |
// TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL i-?simo. |
... | ... | |
245 | 246 |
|
246 | 247 |
if (toNode.getStatus() != GvNode.statNowInList) { |
247 | 248 |
toNode.setStatus(GvNode.statNowInList); |
248 |
pq.insert_or_dec_key(toNode, newCost); |
|
249 |
toNode.setStimation(newCost); |
|
250 |
pq.add(toNode); |
|
249 | 251 |
//candidatos.add(toNode); |
250 | 252 |
} |
251 | 253 |
} // Si hay mejora |
Also available in: Unified diff