Class ShortestPaths
All methods operate on a WeightedGraph<V, E> whose edges
carry an attribute of type E.
The result is a shortest-path tree (SPT): a
Map<V, WeightedEdge<V, E>> where each entry v → edge records
the cheapest incoming edge to v. The start vertex is absent.
Note on Option 3: Dijkstra accumulates path costs — the cost to
reach a vertex is the sum of edge weights along the path. This requires both
a combine function (e.g. addition) and a zero identity
element, unlike Prim and Kruskal which only compare individual edge weights
and need only a Comparator.
Option 1 example (Double weights):
WeightedGraph<String, Double> g = WeightedGraph.directedWeighted();
g.addEdge(new WeightedEdge<>("A", "B", 3.0));
g.addEdge(new WeightedEdge<>("A", "C", 1.0));
g.addEdge(new WeightedEdge<>("C", "B", 1.0));
Map<String, WeightedEdge<String, Double>> spt = ShortestPaths.dijkstra(g, "A");
// spt.get("B").from() == "C" (via C, total cost 2.0)
// spt.get("B").attribute() == 1.0 (the C→B edge weight)
Option 3 example (custom attribute type):
WeightedGraph<Building, TunnelProperties> g = WeightedGraph.directedWeighted();
g.addEdge(new WeightedEdge<>(b1, b2, props));
Map<Building, WeightedEdge<Building, TunnelProperties>> spt =
ShortestPaths.dijkstra(g, start,
(a, b) -> new TunnelProperties(a.cost + b.cost, ...), // combine
TunnelProperties.ZERO, // identity
Comparator.comparingInt(tp -> tp.cost)); // ordering
-
Method Summary
Modifier and TypeMethodDescriptionstatic <V,E> Map <V, WeightedEdge<V, E>> acyclic(WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs the acyclic shortest-paths algorithm with a custom edge attribute type.static <V> Map<V, WeightedEdge<V, Double>> acyclic(WeightedGraph<V, Double> graph, V start) Runs the acyclic shortest-paths algorithm on a directed acyclic graph whose edges carryDoubleweights.static <V,E> Optional <Map<V, WeightedEdge<V, E>>> bellmanFord(WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs the Bellman-Ford algorithm with a custom edge attribute type.static <V> Optional<Map<V, WeightedEdge<V, Double>>> bellmanFord(WeightedGraph<V, Double> graph, V start) Runs the Bellman-Ford algorithm on a graph whose edges carryDoubleweights.static <V,E> Map <V, WeightedEdge<V, E>> dijkstra(WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs Dijkstra's algorithm with a custom edge attribute type.static <V> Map<V, WeightedEdge<V, Double>> dijkstra(WeightedGraph<V, Double> graph, V start) Runs Dijkstra's algorithm on a graph whose edges carryDoubleweights.
-
Method Details
-
dijkstra
Runs Dijkstra's algorithm on a graph whose edges carryDoubleweights.Costs are combined by addition; edges are ordered by natural
Doubleordering. No configuration required.The graph must be directed.
- Type Parameters:
V- the vertex type.- Parameters:
graph- a directedWeightedGraph<V, Double>.start- the source vertex.- Returns:
- the SPT as
Map<V, WeightedEdge<V, Double>>; the start vertex is absent. - Throws:
IllegalStateException- ifgraphis undirected.
-
dijkstra
public static <V,E> Map<V,WeightedEdge<V, dijkstraE>> (WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs Dijkstra's algorithm with a custom edge attribute type.Because Dijkstra accumulates path costs, the caller must supply:
combine— how to add two costs (e.g. integer addition)zero— the identity element forcombine(e.g.0for addition)comparator— how to order costs
The graph must be directed.
- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- a directedWeightedGraph<V, E>.start- the source vertex.combine- accumulates two costs into one.zero- the identity element forcombine.comparator- orders costs.- Returns:
- the SPT as
Map<V, WeightedEdge<V, E>>; the start vertex is absent. - Throws:
IllegalStateException- ifgraphis undirected.
-
bellmanFord
public static <V> Optional<Map<V,WeightedEdge<V, bellmanFordDouble>>> (WeightedGraph<V, Double> graph, V start) Runs the Bellman-Ford algorithm on a graph whose edges carryDoubleweights.Unlike
dijkstra(WeightedGraph, Object), Bellman-Ford accepts negative edge weights. It cannot give an answer when a negative cycle is reachable fromstart— every path round such a cycle is cheaper than the last, so no shortest path exists — and reports that by returning an emptyOptional.The graph must be directed.
- Type Parameters:
V- the vertex type.- Parameters:
graph- a directedWeightedGraph<V, Double>.start- the source vertex.- Returns:
- the SPT as
Map<V, WeightedEdge<V, Double>>with the start vertex absent, or an emptyOptionalif a negative cycle is reachable fromstart. - Throws:
IllegalStateException- ifgraphis undirected.
-
bellmanFord
public static <V,E> Optional<Map<V,WeightedEdge<V, bellmanFordE>>> (WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs the Bellman-Ford algorithm with a custom edge attribute type.Like Dijkstra, Bellman-Ford accumulates path costs, so
combineandzeroare required as well ascomparator.- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- a directedWeightedGraph<V, E>.start- the source vertex.combine- accumulates two costs into one.zero- the identity element forcombine.comparator- orders costs.- Returns:
- the SPT, or an empty
Optionalif a negative cycle is reachable fromstart. - Throws:
IllegalStateException- ifgraphis undirected.
-
acyclic
Runs the acyclic shortest-paths algorithm on a directed acyclic graph whose edges carryDoubleweights.Relaxing edges in topological order visits each edge once, so this is linear in the size of the graph — faster than both Dijkstra and Bellman-Ford. Negative weights are allowed, since a DAG has no cycles for them to make cheaper.
The graph must be directed and acyclic. Test with
TopologicalSort.isDAG(Graph)if you are not sure.- Type Parameters:
V- the vertex type.- Parameters:
graph- a directed acyclicWeightedGraph<V, Double>.start- the source vertex.- Returns:
- the SPT as
Map<V, WeightedEdge<V, Double>>; the start vertex is absent. - Throws:
IllegalStateException- ifgraphis undirected.IllegalArgumentException- ifgraphcontains a cycle.
-
acyclic
public static <V,E> Map<V,WeightedEdge<V, acyclicE>> (WeightedGraph<V, E> graph, V start, BinaryOperator<E> combine, E zero, Comparator<E> comparator) Runs the acyclic shortest-paths algorithm with a custom edge attribute type.- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- a directed acyclicWeightedGraph<V, E>.start- the source vertex.combine- accumulates two costs into one.zero- the identity element forcombine.comparator- orders costs.- Returns:
- the SPT; the start vertex is absent.
- Throws:
IllegalStateException- ifgraphis undirected.IllegalArgumentException- ifgraphcontains a cycle.
-