com.mhhe.clrs2e
Class Dijkstra

java.lang.Object
  |
  +--com.mhhe.clrs2e.SingleSourceShortestPaths
        |
        +--com.mhhe.clrs2e.Dijkstra

public class Dijkstra

extends SingleSourceShortestPaths

Implementation of Dijkstra's algorithm on page 595 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

Dijkstra.DijkstraInfo Inner class to maintain the Vertex object, key, parent, and handle into the priority queue for each vertex.

Field Summary

Fields inherited from class com.mhhe.clrs2e.SingleSourceShortestPaths

g, noNegWeightCycle

Constructor Summary

Dijkstra(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph)
Sets up the instance variables, including allocation of the spInfo array but not allocation of the ShortestPathInfo objects referenced by the array.

Method Summary

void	computeShortestPaths(com.mhhe.clrs2e.Vertex s) Computes single-source shortest paths from a given source vertex, filling in weights and predecessors in the spInfo array.
protected com.mhhe.clrs2e.ShortestPathInfo	newShortestPathInfo() Returns a new DijkstraInfo object, overriding SingleSourceShortestPaths.newShortestPathInfo().

Methods inherited from class com.mhhe.clrs2e.SingleSourceShortestPaths

getShortestPathInfo, getShortestPathInfo, hasNoNegativeWeightCycle, initializeSingleSource

Methods inherited from class java.lang.Object

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

Constructor Detail

Dijkstra

public Dijkstra(com.mhhe.clrs2e.WeightedAdjacencyListGraph theGraph)

Sets up the instance variables, including allocation of the spInfo array but not allocation of the ShortestPathInfo objects referenced by the array. (That's SingleSourceShortestPaths.initializeSingleSource(com.mhhe.clrs2e.Vertex)'s job.)

Parameters:

theGraph - The graph for which we are computing single-source shortest paths.

Method Detail

computeShortestPaths

public void computeShortestPaths(com.mhhe.clrs2e.Vertex s)

Computes single-source shortest paths from a given source vertex, filling in weights and predecessors in the spInfo array.

Specified by:

computeShortestPaths in class SingleSourceShortestPaths

Parameters:

s - The source vertex.

newShortestPathInfo

protected com.mhhe.clrs2e.ShortestPathInfo newShortestPathInfo()

Returns a new DijkstraInfo object, overriding SingleSourceShortestPaths.newShortestPathInfo().

Overrides:

newShortestPathInfo in class SingleSourceShortestPaths