net.junaraki.annobase.util.graph

Class DijkstraShortestPath

java.lang.Object

net.junaraki.annobase.util.graph.DijkstraShortestPath

public class DijkstraShortestPath
extends java.lang.Object

This class provides Dijkstra's algorithm. It solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative.

Author:

Jun Araki

Constructor Summary

Constructors

Constructor and Description
DijkstraShortestPath()

Method Summary

Modifier and Type	Method and Description
static <V,E> java.util.List<V>	getShortestPath(Graph<V,E> graph, V src, V dest) Returns the shortest path from the given source vertex to the given destination vertex using the Dijkstra algorithm.

Methods inherited from class java.lang.Object

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

Constructor Detail

DijkstraShortestPath

public DijkstraShortestPath()

Method Detail

getShortestPath

public static <V,E> java.util.List<V> getShortestPath(Graph<V,E> graph,
                                                      V src,
                                                      V dest)

Returns the shortest path from the given source vertex to the given destination vertex using the Dijkstra algorithm. This method returns the shortest path as a list of vertexes. An empty list means that the two vertices are the same.

Parameters:

graph -

src -

dest -

Returns: