|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.datastructures.Dijkstra<V,E>
public class Dijkstra<V,E>
Dijkstra's algorithm for the single-source shortest path problem in an undirected graph whose edges have integer weights.
To execute the algorithm, use the execute
method, and then make
subsequent calls to the getDist
method to
obtain the shortest distance from the start to any given vertex.
Field Summary | |
---|---|
protected java.lang.Object |
DIST
Decoration key for vertex distances |
protected java.lang.Object |
ENTRY
Decoration key for entries in the priority queue |
protected net.datastructures.Graph<V,E> |
graph
Input graph. |
protected static java.lang.Integer |
INFINITE
Infinity value. |
protected net.datastructures.AdaptablePriorityQueue<java.lang.Integer,net.datastructures.Vertex<V>> |
Q
Auxiliary priority queue. |
protected java.lang.Object |
WEIGHT
Decoration key for edge weights |
Constructor Summary | |
---|---|
Dijkstra()
|
Method Summary | |
---|---|
protected void |
dijkstraVisit(net.datastructures.Vertex<V> v)
The actual execution of Dijkstra's algorithm. |
void |
execute(net.datastructures.Graph<V,E> g,
net.datastructures.Vertex<V> s,
java.lang.Object w)
Executes Dijkstra's algorithm. |
int |
getDist(net.datastructures.Vertex<V> u)
Get the distance of a vertex from the source vertex. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected static final java.lang.Integer INFINITE
protected net.datastructures.Graph<V,E> graph
protected java.lang.Object WEIGHT
protected java.lang.Object DIST
protected java.lang.Object ENTRY
protected net.datastructures.AdaptablePriorityQueue<java.lang.Integer,net.datastructures.Vertex<V>> Q
Constructor Detail |
---|
public Dijkstra()
Method Detail |
---|
public void execute(net.datastructures.Graph<V,E> g, net.datastructures.Vertex<V> s, java.lang.Object w)
g
- Input graphs
- Source vertexw
- Weight decoration objectpublic int getDist(net.datastructures.Vertex<V> u)
execute
has been called.
//begin#fragment execute
u
- Start vertex for the shortest path treeprotected void dijkstraVisit(net.datastructures.Vertex<V> v)
v
- source vertex.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |