mxICostFunction cf, int steps, boolean directed)
{
// Sets up a pqueue and a hashtable to store the predecessor for each
// cell in tha graph traversal. The pqueue is initialized
// with the from element at prio 0.
mxGraphView view = graph.getView();
mxFibonacciHeap q = createPriorityQueue();
Hashtable<Object, Object> pred = new Hashtable<Object, Object>();
q.decreaseKey(q.getNode(from, true), 0); // Inserts automatically
// The main loop of the dijkstra algorithm is based on the pqueue being
// updated with the actual shortest distance to the source vertex.
for (int j = 0; j < steps; j++)
{
mxFibonacciHeap.Node node = q.removeMin();
double prio = node.getKey();
Object obj = node.getUserObject();
// Exits the loop if the target node or vertex has been reached
if (obj == to)
{
break;
}
// Gets all outgoing edges of the closest cell to the source
Object[] e = (directed) ? graph.getOutgoingEdges(obj) : graph
.getConnections(obj);
if (e != null)
{
for (int i = 0; i < e.length; i++)
{
Object[] opp = graph.getOpposites(new Object[] { e[i] },
obj);
if (opp != null && opp.length > 0)
{
Object neighbour = opp[0];
// Updates the priority in the pqueue for the opposite node
// to be the distance of this step plus the cost to
// traverese the edge to the neighbour. Note that the
// priority queue will make sure that in the next step the
// node with the smallest prio will be traversed.
if (neighbour != null && neighbour != obj
&& neighbour != from)
{
double newPrio = prio
+ ((cf != null) ? cf.getCost(view
.getState(e[i])) : 1);
node = q.getNode(neighbour, true);
double oldPrio = node.getKey();
if (newPrio < oldPrio)
{
pred.put(neighbour, e[i]);
q.decreaseKey(node, newPrio);
}
}
}
}
}
if (q.isEmpty())
{
break;
}
}
// Constructs a path array by walking backwards through the predessecor
// map and filling up a list of edges, which is subsequently returned.
ArrayList<Object> list = new ArrayList<Object>(2 * steps);
Object obj = to;
Object edge = pred.get(obj);
if (edge != null)
{
list.add(obj);
while (edge != null)
{
list.add(0, edge);
boolean isSource = view.getVisibleTerminal(edge, true) == obj;
obj = view.getVisibleTerminal(edge, !isSource);
list.add(0, obj);
edge = pred.get(obj);
}
}