mascoptLib.algos.abstractalgos
Class Dijkstra

java.lang.Object
  mascoptLib.algos.abstractalgos.StepAlgo
      mascoptLib.algos.abstractalgos.Dijkstra

All Implemented Interfaces:

Runnable

public class Dijkstra

extends StepAlgo

Provides a simple algorithm to find distance from a node and the paths corresponding to this node.

After constructing the dijkstra object, two steps are necessary to obtains shortest paths or distances. Choose a node from where you want to compute distances and launch valuateFromSource. Then, you can access the values via other access methods.

Note that DISTANCE_MAX is a constant representing the maximum distance beetween two nodes (modelize the infinite value). It can be a serious limitation for the use of algorithm.

The distance on edges are read with getValue with the parameter DIJKSTRADISTANCE. You can change this string to another string to read another value.

Note that all values on edges must be stored as string.

See Also:

valuateFromSource

Field Summary

String

DIJKSTRADISTANCE The string which identify the value to consider as the distance on edges.

Constructor Summary

Dijkstra(AbstractGraph g)
Default constructor.

Method Summary

Hashtable	getDistances() Returns the hashtable giving distances.
int	getDistanceTo(AbstractVertex v) Returns the distance from source of a node.
AbstractPath	getShortestPathTo(AbstractVertex v) Returns the chain form source to node v.
AbstractVertex	getStartNode() Returns the current starting node.
void	run() Computes the shortest distances and paths from vertex u.
void	slowAlgorithm(boolean slow)
void	valuateFromSource(AbstractVertex u) Computes the shortest distances and paths from node u.

Methods inherited from class mascoptLib.algos.abstractalgos.StepAlgo

byStep, ends, isDemo, isEnded, nextStep, setTime, start, waitB

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DIJKSTRADISTANCE

public String DIJKSTRADISTANCE

The string which identify the value to consider as the distance on edges. You can easily change it to compute shortests paths with another distance.

Constructor Detail

Dijkstra

public Dijkstra(AbstractGraph g)

Default constructor. When constructed, execute the valuateFromSource function to compute the distances and path and then, get these results via other access method of the class.

Parameters:

g - the graph used by Dijkstra algorithm

Method Detail

valuateFromSource

public void valuateFromSource(AbstractVertex u)

Computes the shortest distances and paths from node u.

Parameters:

u - the abstractnode source from where computing distances

slowAlgorithm

public void slowAlgorithm(boolean slow)

run

public void run()

Computes the shortest distances and paths from vertex u.

Specified by:

run in interface Runnable

Specified by:

run in class StepAlgo

getDistances

public Hashtable getDistances()

Returns the hashtable giving distances. The key of hashtable is the node. Giving a node returns an integer representing distance from source.

Returns:

the hashtable which keys are nodes and containing all distances from source node.

getDistanceTo

public int getDistanceTo(AbstractVertex v)

Returns the distance from source of a node.

Parameters:

v - the node wanted to know the distance.

Returns:

the distance in an integer value.

getShortestPathTo

public AbstractPath getShortestPathTo(AbstractVertex v)

Returns the chain form source to node v.

Parameters:

v - the node ending the shortest chain starting at source node.

Returns:

the chain form source to node v.

getStartNode

public AbstractVertex getStartNode()

Returns the current starting node.

Returns:

the current starting node from where to compute..