Package com.jgalgo.alg.shortestpath

Interface ShortestPathSingleSource

  • All Known Implementing Classes:
    ShortestPathSingleSourceAbstract, ShortestPathSingleSourceBellmanFord, ShortestPathSingleSourceCardinality, ShortestPathSingleSourceDag, ShortestPathSingleSourceDial, ShortestPathSingleSourceDijkstra, ShortestPathSingleSourceGoldberg
    public interface ShortestPathSingleSource
    Single Source Shortest Path algorithm.

    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 all other vertices in \(V\), where the 'shortest' is defined by comparing the sum of edges weights of each path. A Single Source Shortest Path (SSSP) is able to compute these shortest paths from a source to any other vertex, along with the distances, which are the shortest paths lengths (weights).

    The most basic single source shortest path (SSSP) algorithms work on graphs with non negative weights, and they are the most efficient, such as Dijkstra algorithm. Negative weights are supported by some implementations of SSSP, and the 'shortest path' is well defined as long as there are no negative cycle in the graph as a path can loop in the cycle and achieve arbitrary small 'length'. When the weights are allowed be negative, algorithms will either find the shortest path to any other vertex, or will find a negative cycle, see NegativeCycleException. Note that if a negative cycle exists, but it is not reachable from the source, the algorithm may or may not find it, depending on the implementation. To get an algorithm instance that support negative weights, use ShortestPathSingleSource.Builder.negativeWeights(boolean).

    A special case of the SSSP problem is on directed graphs that does not contain any cycles, and it could be solved in linear time for any weights types by calculating the topological order of the vertices (see ShortestPathSingleSource.Builder.dag(boolean)). Another special case arise when the weight function assign \(1\) to any edges, and the shortest paths could be computed again in linear time using a BFS (see ShortestPathSingleSource.Builder.cardinality(boolean)).

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

     
 // Create an undirected graph with three vertices and edges between them
 Graph<String, Integer> g = Graph.newUndirected();
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);
 g.addEdge("Dresden", "Leipzig", 14);

 // Assign some weights to the edges
 WeightsDouble<Integer> w = g.addEdgesWeights("distance-km", double.class);
 w.set(9, 191.1);
 w.set(13, 193.3);
 w.set(14, 121.3);

 // Calculate the shortest paths from Berlin to all other cities
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newInstance();
 ShortestPathSingleSource.Result<String, Integer> ssspRes = ssspAlgo.computeShortestPaths(g, w, "Berlin");

 // Print the shortest path from Berlin to Leipzig
 System.out.println("Distance from Berlin to Leipzig is: " + ssspRes.distance("Leipzig"));
 System.out.println("The shortest path from Berlin to Leipzig is:");
 for (Integer e : ssspRes.getPath("Leipzig").edges()) {
 	String u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav
    See Also:
    ShortestPathAllPairs, Wikipedia

    • Method Detail

      • computeShortestPaths

        <V,​E> ShortestPathSingleSource.Result<V,​E> computeShortestPaths​(Graph<V,​E> g,
                                                                            WeightFunction<E> w,
                                                                            V source)
        Compute the shortest paths from a source to any other vertex in a graph.

        Given an edge weight function, the length of a path is the weight sum of all edges of the path. The shortest path from a source vertex to some other vertex is the path with the minimum weight. For cardinality (non weighted) shortest path, pass null instead of the weight function w.

        If g is an IntGraph, a ShortestPathSingleSource.IResult 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 - a graph
        w - an edge weight function
        source - a source vertex
        Returns:
        a result object containing the distances and shortest paths from the source to any other vertex
        Throws:
        NegativeCycleException - if a negative cycle is detected in the graph. If there is a negative cycle that is not reachable from the given source, it might not be detected, depending on the implementation