net.datastructures
Class Dijkstra

java.lang.Object
  net.datastructures.Dijkstra

public class Dijkstra

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 Attribute for vertex distances
protected Object	ENTRY Decoration key for entries in the priority queue
protected Graph	graph Input graph.
static int	INFINITE Infinity value.
protected AdaptablePriorityQueue	Q Auxiliary priority queue.
protected Object	WEIGHT Decoration key for edge weights

Constructor Summary

Dijkstra()

Method Summary

protected void	dijkstraVisit(Vertex v) The actual execution of Dijkstra's algorithm.
void	execute(Graph g, Vertex s, Object w) Executes Dijkstra's algorithm.
protected int	getDist(Entry e) Get the distance of a vertex given its entry
int	getDist(Vertex u) Get the distance of a vertex from the source vertex.
protected Entry	getEntry(Vertex v) Get the entry decoration of a vertex.
protected Vertex	getVertex(Entry e) Get the vertex associated with an entry
protected void	removeEntry(Vertex v) Remove the entry decoration of a vertex
protected void	setDist(Vertex v, int d) Set the distance of a vertex.
protected void	setEntry(Vertex v, Entry e) Set the entry decoration of a vertex
protected int	weight(Edge e) Get the weight of an edge

Methods inherited from class java.lang.Object

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

Field Detail

INFINITE

public static final int INFINITE

Infinity value.

See Also:

Constant Field Values

graph

protected Graph graph

Input graph.

WEIGHT

protected Object WEIGHT

Decoration key for edge weights

Q

protected AdaptablePriorityQueue Q

Auxiliary priority queue.

DIST

protected Object DIST

Attribute for vertex distances

ENTRY

protected Object ENTRY

Decoration key for entries in the priority queue

Constructor Detail

Dijkstra

public Dijkstra()

Method Detail

execute

public void execute(Graph g,
                    Vertex s,
                    Object w)

Executes Dijkstra's algorithm.

Parameters:

g - Input graph

s - Source vertex

w - Weight decoration object

getDist

public int getDist(Vertex u)

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

Parameters:

u - Start vertex for the shortest path tree

dijkstraVisit

protected void dijkstraVisit(Vertex v)

The actual execution of Dijkstra's algorithm.

Parameters:

v - source vertex.

weight

protected int weight(Edge e)

Get the weight of an edge

setDist

protected void setDist(Vertex v,
                       int d)

Set the distance of a vertex.

getEntry

protected Entry getEntry(Vertex v)

Get the entry decoration of a vertex.

setEntry

protected void setEntry(Vertex v,
                        Entry e)

Set the entry decoration of a vertex

removeEntry

protected void removeEntry(Vertex v)

Remove the entry decoration of a vertex

getVertex

protected Vertex getVertex(Entry e)

Get the vertex associated with an entry

getDist

protected int getDist(Entry e)

Get the distance of a vertex given its entry