slib.graph.algo.shortest_path

Class Dijkstra

java.lang.Object

slib.graph.algo.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:

Sébastien Harispe

Field Summary

Fields

Modifier and Type	Field and Description
static Double	NOT_COMPUTED

Constructor Summary

Constructors

Constructor and Description
Dijkstra(G g, WalkConstraint walconstraints) Edge weights set to 1
Dijkstra(G g, WalkConstraint walconstraints, GWS weightingScheme) Create an Dijkstra algorithm used to compute shortest paths on a graph considering a given non negative weighting scheme

Method Summary

Methods

Modifier and Type	Method and Description
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

Field Detail

NOT_COMPUTED

public static final Double NOT_COMPUTED

Constructor Detail

Dijkstra

public Dijkstra(G g,
        WalkConstraint walconstraints)
         throws SLIB_Ex_Critic

Edge weights set to 1

Parameters:

g -

walconstraints -

Throws:

SLIB_Ex_Critic

Dijkstra

public Dijkstra(G g,
        WalkConstraint walconstraints,
        GWS weightingScheme)
         throws 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

walconstraints - the constraint associated to the search

weightingScheme - a

Throws:

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:

a Map containing the shortest path from the given source to the other vertices of the graph.