Package edu.uci.ics.jung.algorithms.shortestpath
Provides interfaces and classes for calculating (geodesic) distances and shortest paths. Currently includes:
DijkstraDistance
: finds the distances from a specified source vertex to other vertices in a weighted graph with no negative cyclesDijkstraShortestPath
: extendsDijkstraDistance
, also finds shortest pathsDistance
: an interface for defining vertex-vertex distancesPrimMinimumSpanningTree
: identifies the spanning tree for a graph of least total edge weightShortestPath
: an interface for shortest-path algorithmsShortestPathUtils
: utility functions for manipulating shortest pathsUnweightedShortestPath
: finds the distances from a specified source vertex to other vertices in an unweighted graph
-
Interface Summary Interface Description Distance<V> An interface for classes which calculate the distance between one vertex and another.ShortestPath<V,E> An interface for algorithms that calculate shortest paths. -
Class Summary Class Description BFSDistanceLabeler<V,E> Labels each node in the graph according to the BFS distance from the start node(s).DijkstraDistance<V,E> Calculates distances in a specified graph, using Dijkstra's single-source-shortest-path algorithm.DijkstraDistance.VertexComparator<V> Compares according to distances, so that the BinaryHeap knows how to order the tree.DijkstraShortestPath<V,E> Calculates distances and shortest paths using Dijkstra's single-source-shortest-path algorithm.DistanceStatistics Statistics relating to vertex-vertex distances in a graph.MinimumSpanningForest<V,E> For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.MinimumSpanningForest2<V,E> For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.PrimMinimumSpanningTree<V,E> For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.ShortestPathUtils Utilities relating to the shortest paths in a graph.UnweightedShortestPath<V,E> Computes the shortest path distances for graphs whose edges are not weighted (using BFS).