Interface ShortestPathST


  • public interface ShortestPathST
    An algorithm for computing the shortest path between two vertices in a graph.

    Given a graph \(G=(V,E)\), and a weight function \(w:E \rightarrow R\), one might ask what is the shortest path from a source vertex to a target vertex, where the 'shortest' is defined by comparing the sum of edges weights of each path. This interface computes such a path. It differ from the more known ShortestPathSingleSource, as it does not compute the paths from a source to all vertices, only to a specific target. This might be more efficient in some cases, as less than linear time and space can be used.

    A variant with a heuristic distance function is also available, see ShortestPathHeuristicST.

    Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

    Author:
    Barak Ugav
    See Also:
    ShortestPathSingleSource, ShortestPathAllPairs, ShortestPathHeuristicST
    • Method Detail

      • computeShortestPath

        <V,​E> Path<V,​E> computeShortestPath​(Graph<V,​E> g,
                                                        WeightFunction<E> w,
                                                        V source,
                                                        V target)
        Compute the shortest path from a source vertex to a target vertex.

        If g is an IntGraph, a IPath object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        w - an edge weight function
        source - the source vertex
        target - the target vertex
        Returns:
        the shortest path from the source to the target, or null if there is no path
      • newInstance

        static ShortestPathST newInstance()
        Create a new S-T shortest path algorithm object.

        This is the recommended way to instantiate a new ShortestPathST object. The ShortestPathST.Builder might support different options to obtain different implementations.

        Returns:
        a default implementation of ShortestPathST