slib.sglib.algo.graph.shortest_path
Class Dijkstra

java.lang.Object
  extended by slib.sglib.algo.graph.shortest_path.Dijkstra

public class Dijkstra
extends Object

Basic implementation of the shortest path algorithm proposed by Dijkstra Only suited for shortest path exclusively composed of non-negative weight more about TODO optimize i.e Fibonacci heap implementation

Author:
Sebastien Harispe

Constructor Summary
Dijkstra(slib.sglib.model.graph.G g, slib.sglib.model.graph.utils.WalkConstraint walconstraints)
          Edge weights set to 1
Dijkstra(slib.sglib.model.graph.G g, slib.sglib.model.graph.utils.WalkConstraint walconstraints, slib.sglib.model.graph.weight.GWS weightingScheme)
          Create an Dijkstra algorithm used to compute shortest paths on a graph considering a given non negative weighting scheme
 
Method Summary
 ConcurrentHashMap<org.openrdf.model.URI,Double> shortestPath(org.openrdf.model.URI source)
           
 Double shortestPath(org.openrdf.model.URI source, org.openrdf.model.URI t)
          Compute shortest path between two nodes Note also that the resultStack is populated during computation
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Dijkstra

public Dijkstra(slib.sglib.model.graph.G g,
                slib.sglib.model.graph.utils.WalkConstraint walconstraints)
         throws slib.utils.ex.SLIB_Ex_Critic
Edge weights set to 1

Parameters:
g -
walconstraints -
Throws:
slib.utils.ex.SLIB_Ex_Critic

Dijkstra

public Dijkstra(slib.sglib.model.graph.G g,
                slib.sglib.model.graph.utils.WalkConstraint walconstraints,
                slib.sglib.model.graph.weight.GWS weightingScheme)
         throws slib.utils.ex.SLIB_Ex_Critic
Create an Dijkstra algorithm used to compute shortest paths on a graph considering a given non negative weighting scheme

Parameters:
g - the graph on which the shortest path has to be computed
setEdgeTypes - the set of edge types to consider
weightingScheme - a
Throws:
slib.utils.ex.SLIB_Ex_Critic
Method Detail

shortestPath

public Double shortestPath(org.openrdf.model.URI source,
                           org.openrdf.model.URI t)
Compute shortest path between two nodes Note also that the resultStack is populated during computation

Parameters:
source -
t -
Returns:
the shortest path weight as double

shortestPath

public ConcurrentHashMap<org.openrdf.model.URI,Double> shortestPath(org.openrdf.model.URI source)
Parameters:
source -
Returns:


Copyright © 2013. All Rights Reserved.