net.datastructures
Class Dijkstra<V,E>

java.lang.Object
  net.datastructures.Dijkstra<V,E>

public class Dijkstra<V,E>
extends 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.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Field Summary

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

Constructor Summary

Dijkstra()

Method Summary

protected void	dijkstraVisit(Vertex<V> v) The actual execution of Dijkstra's algorithm.
void	execute(Graph<V,E> g, Vertex<V> s, 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 Integer INFINITE

Infinity value.

graph

protected Graph<V,E> graph

Input graph.

WEIGHT

protected Object WEIGHT

Decoration key for edge weights

DIST

protected Object DIST

Decoration key for vertex distances

ENTRY

protected Object ENTRY

Decoration key for entries in the priority queue

Q

protected AdaptablePriorityQueue<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,
                    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.