com.savarese.algorithms.graph
Class DijkstraShortestPathFinder<V,E extends Edge<V,java.lang.Integer>>

java.lang.Object
  com.savarese.algorithms.graph.DijkstraShortestPathFinder<V,E>

All Implemented Interfaces:

SingleSourcePathFinder<V,java.lang.Integer,E>

public class DijkstraShortestPathFinder<V,E extends Edge<V,java.lang.Integer>>
extends java.lang.Object
implements SingleSourcePathFinder<V,java.lang.Integer,E>

The DijkstraShortestPathFinder class implements Dijkstra's algorithm, which solves the single source shortest paths problem. It finds all the shortest paths between a source vertex and every other vertex in a graph.

Author:

Daniel F. Savarese

Field Summary

static int

INFINITY

Constructor Summary

DijkstraShortestPathFinder()

Method Summary

SingleSourcePath<V,java.lang.Integer>

findPath(Graph<V,E> graph, V source) Finds all the shortest paths in the given graph between the given source vertex and all other vertices in the graph.

Methods inherited from class java.lang.Object

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

Field Detail

INFINITY

public static final int INFINITY

See Also:

Constant Field Values

Constructor Detail

DijkstraShortestPathFinder

public DijkstraShortestPathFinder()

Method Detail

findPath

public SingleSourcePath<V,java.lang.Integer> findPath(Graph<V,E> graph,
                                                      V source)

Finds all the shortest paths in the given graph between the given source vertex and all other vertices in the graph.

Specified by:

findPath in interface SingleSourcePathFinder<V,java.lang.Integer,E extends Edge<V,java.lang.Integer>>

Parameters:

graph - The graph to be searched.

source - The source vertex from which all paths will emanate.

Returns:

The paths found.