|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objecthelix.graph.algo.Dijkstra
public class Dijkstra
Dijkstra's algorithm solves the single-source shortest path problem note1 : this implementation is O(V2 + E) i.e does not use a priority queue note2: Dijkstra's algorithm is only useful if you want the shortest path from one source. In case you want all pairwise distances, you may consider the Floyd-Warshall algorithm instead.
Field Summary | |
---|---|
static String |
Distance
|
Constructor Summary | |
---|---|
Dijkstra(Graph graph)
constructor |
Method Summary | |
---|---|
int |
distance(Vertex target)
get distance from source to target return -1 if target is not connected to source |
Vertex |
getSource()
get current source |
void |
run(Vertex source)
main Dijkstra algorithm get all distances from source to all vertices in connected component of source (CC(source)) distance are stored into vertices registry with label Dijkstra.Distance note: vertices not in CC(source) do not have the Dijkstra.Distance flag |
List<Vertex> |
shortestPath(Vertex target)
get shortest path from source to target return a list [source, ..., target] or empty list if there is no path |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public static final String Distance
Constructor Detail |
---|
public Dijkstra(Graph graph)
Method Detail |
---|
public void run(Vertex source)
public Vertex getSource()
public int distance(Vertex target)
public List<Vertex> shortestPath(Vertex target)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |