net.datastructures

Class Dijkstra<V,E>

java.lang.Object

net.datastructures.Dijkstra<V,E>

public class Dijkstra<V,E>
extends java.lang.Object

Dijkstra's algorithm for the single-source shortest path problem in an undirected graph whose edges have integer weights.

To execute the algorithm, use the execute method, and then make subsequent calls to the getDist method to obtain the shortest distance from the start to any given vertex.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.lang.Object	DIST Decoration key for vertex distances
protected java.lang.Object	ENTRY Decoration key for entries in the priority queue
protected Graph<V,E>	graph Input graph.
protected static java.lang.Integer	INFINITE Infinity value.
protected AdaptablePriorityQueue<java.lang.Integer,Vertex<V>>	Q Auxiliary priority queue.
protected java.lang.Object	WEIGHT Decoration key for edge weights

Constructor Summary

Constructors

Constructor and Description
Dijkstra()

Method Summary

Modifier and Type	Method and Description
protected void	dijkstraVisit(Vertex<V> v) The actual execution of Dijkstra's algorithm.
void	execute(Graph<V,E> g, Vertex<V> s, java.lang.Object w) Executes Dijkstra's algorithm.
int	getDist(Vertex<V> u) Get the distance of a vertex from the source vertex.

Methods inherited from class java.lang.Object

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

Field Detail

INFINITE

protected static final java.lang.Integer INFINITE

Infinity value.

graph

protected Graph<V,E> graph

Input graph.

WEIGHT

protected java.lang.Object WEIGHT

Decoration key for edge weights

DIST

protected java.lang.Object DIST

Decoration key for vertex distances

ENTRY

protected java.lang.Object ENTRY

Decoration key for entries in the priority queue

Q

protected AdaptablePriorityQueue<java.lang.Integer,Vertex<V>> Q

Auxiliary priority queue.

Constructor Detail

Dijkstra

public Dijkstra()

Method Detail

execute

public void execute(Graph<V,E> g,
                    Vertex<V> s,
                    java.lang.Object w)

Executes Dijkstra's algorithm.

Parameters:

g - Input graph

s - Source vertex

w - Weight decoration object

getDist

public int getDist(Vertex<V> u)

Get the distance of a vertex from the source vertex. //end#fragment execute This method returns the length of a shortest path from the source to u after execute has been called. //begin#fragment execute

Parameters:

u - Start vertex for the shortest path tree

dijkstraVisit

protected void dijkstraVisit(Vertex<V> v)

The actual execution of Dijkstra's algorithm.

Parameters:

v - source vertex.