Class ShortestPaths

java.lang.Object
com.phasmidsoftware.gryphon.java.ShortestPaths

public class ShortestPaths extends Object
Java façade for shortest-path algorithms on weighted directed graphs.

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 Details

    • dijkstra

      public static <V> Map<V,WeightedEdge<V,Double>> dijkstra(WeightedGraph<V,Double> graph, V start)
      Runs Dijkstra's algorithm on a graph whose edges carry Double weights.

      Costs are combined by addition; edges are ordered by natural Double ordering. No configuration required.

      The graph must be directed.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - a directed WeightedGraph<V, Double>.
      start - the source vertex.
      Returns:
      the SPT as Map<V, WeightedEdge<V, Double>>; the start vertex is absent.
      Throws:
      IllegalStateException - if graph is undirected.
    • dijkstra

      public 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.

      Because Dijkstra accumulates path costs, the caller must supply:

      • combine — how to add two costs (e.g. integer addition)
      • zero — the identity element for combine (e.g. 0 for 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 directed WeightedGraph<V, E>.
      start - the source vertex.
      combine - accumulates two costs into one.
      zero - the identity element for combine.
      comparator - orders costs.
      Returns:
      the SPT as Map<V, WeightedEdge<V, E>>; the start vertex is absent.
      Throws:
      IllegalStateException - if graph is undirected.
    • bellmanFord

      public 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 carry Double weights.

      Unlike dijkstra(WeightedGraph, Object), Bellman-Ford accepts negative edge weights. It cannot give an answer when a negative cycle is reachable from start — every path round such a cycle is cheaper than the last, so no shortest path exists — and reports that by returning an empty Optional.

      The graph must be directed.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - a directed WeightedGraph<V, Double>.
      start - the source vertex.
      Returns:
      the SPT as Map<V, WeightedEdge<V, Double>> with the start vertex absent, or an empty Optional if a negative cycle is reachable from start.
      Throws:
      IllegalStateException - if graph is undirected.
    • bellmanFord

      public 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.

      Like Dijkstra, Bellman-Ford accumulates path costs, so combine and zero are required as well as comparator.

      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      graph - a directed WeightedGraph<V, E>.
      start - the source vertex.
      combine - accumulates two costs into one.
      zero - the identity element for combine.
      comparator - orders costs.
      Returns:
      the SPT, or an empty Optional if a negative cycle is reachable from start.
      Throws:
      IllegalStateException - if graph is undirected.
    • acyclic

      public 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 carry Double weights.

      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 acyclic WeightedGraph<V, Double>.
      start - the source vertex.
      Returns:
      the SPT as Map<V, WeightedEdge<V, Double>>; the start vertex is absent.
      Throws:
      IllegalStateException - if graph is undirected.
      IllegalArgumentException - if graph contains a cycle.
    • acyclic

      public static <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.
      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      graph - a directed acyclic WeightedGraph<V, E>.
      start - the source vertex.
      combine - accumulates two costs into one.
      zero - the identity element for combine.
      comparator - orders costs.
      Returns:
      the SPT; the start vertex is absent.
      Throws:
      IllegalStateException - if graph is undirected.
      IllegalArgumentException - if graph contains a cycle.