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.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

Constructor Summary

Constructors

Constructor and Description
Dijkstra()

Method Summary

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

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

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