Interface ShortestPath<T,E>

Type Parameters:
T - graph node type
E - graph edge type
Functional Interface:
This is a functional interface and can therefore be used as the assignment target for a lambda expression or method reference.
@FunctionalInterface public interface ShortestPath<T,E>
Shortest path procedure on a graph.

  • Method Details

    • bfs

      static <T> ShortestPath<T,?> bfs()
      Returns a shortest path procedure which: 
      ignores edge weights
uses breadth-first search to visit nodes
has runtime O(V + E), space O(V) (V = number of nodes, E = number of edges)

    • dijkstra

      static <T, E extends Number & Comparable<E>> ShortestPath<T,E> dijkstra()
      dijkstra(BinaryOperator) with a convenience adder for numerical edges

    • dijkstra

      static <T, E extends Comparable<E>> ShortestPath<T,E> dijkstra(BinaryOperator<E> adder)
      Returns a shortest path procedure which: 
      respects edge weights
uses Dijkstra's algorithm to find a path
has runtime O(E log V), space O(V) (V = number of nodes, E = number of edges)

    • aStar

      static <T, E extends Comparable<E>> ShortestPath<T,E> aStar(BinaryOperator<E> adder, BiFunction<T,T,E> heuristic)
      Returns a shortest path procedure which 
      respects edge weights
uses A* algorithm to find a path
has runtime O(E log V), space O(V) (V = number of nodes, E = number of edges)

    • apply

      List<T> apply(Graph<T,E> graph, T start, T end)
      Returns a list of nodes denoting a shortest path in graph from start to end.