```
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 negative cycles exists, algorithms will either find the shortest path to any other vertex, or will find a negative cycle, see ShortestPathSingleSource.Result.getNegativeCycle(). 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.setNegativeWeights(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.setDag(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.setCardinality(boolean)).
Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() 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

Nested Class Summary

Nested Classes
Modifier and Type	Interface	Description
`static interface`	`ShortestPathSingleSource.Builder`	A builder for `ShortestPathSingleSource` objects.
`static interface`	`ShortestPathSingleSource.IResult`	A result object for the `ShortestPathSingleSource` problem for `IntGraph`.
`static interface`	`ShortestPathSingleSource.Result<V,E>`	A result object for the `ShortestPathSingleSource` problem.

Method Summary

All Methods Static Methods Instance Methods Abstract Methods
Modifier and Type	Method	Description
`<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.
`static ShortestPathSingleSource.Builder`	`newBuilder()`	Create a new single source shortest path algorithm builder.
`static ShortestPathSingleSource`	`newInstance()`	Create a new shortest path algorithm object.

- 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
  - newInstance
```
static ShortestPathSingleSource newInstance()
```
    Create a new shortest path algorithm object.
    This is the recommended way to instantiate a new ShortestPathSingleSource object. The ShortestPathSingleSource.Builder might support different options to obtain different implementations.
    
    Returns:
    
    a default implementation of ShortestPathSingleSource
  - newBuilder
```
static ShortestPathSingleSource.Builder newBuilder()
```
    Create a new single source shortest path algorithm builder.
    Use newInstance() for a default implementation.
    
    Returns:
    
    a new builder that can build ShortestPathSingleSource objects

Interface ShortestPathSingleSource

Nested Class Summary

Method Summary

Method Detail

computeShortestPaths

newInstance

newBuilder