helix.graph.algo
Class Dijkstra

java.lang.Object
  extended by helix.graph.algo.Dijkstra

public class Dijkstra
extends Object

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

Distance

public static final String Distance
See Also:
Constant Field Values
Constructor Detail

Dijkstra

public Dijkstra(Graph graph)
constructor

Method Detail

run

public 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


getSource

public Vertex getSource()
get current source


distance

public int distance(Vertex target)
get distance from source to target return -1 if target is not connected to source


shortestPath

public 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