```
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'. See 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)).
```
 
 // Create a directed graph with three vertices and edges between them
 Graph g = GraphFactory.newDirected().newGraph();
 int v1 = g.addVertex();
 int v2 = g.addVertex();
 int v3 = g.addVertex();
 int e1 = g.addEdge(v1, v2);
 int e2 = g.addEdge(v2, v3);
 int e3 = g.addEdge(v1, v3);

 // Assign some weights to the edges
 Weights.Double w = g.addEdgesWeights("weightsKey", double.class);
 w.set(e1, 1.2);
 w.set(e2, 3.1);
 w.set(e3, 15.1);

 // Calculate the shortest paths from v1 to all other vertices
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newBuilder().build();
 ShortestPathSingleSource.Result ssspRes = ssspAlgo.computeShortestPaths(g, w, v1);

 // Print the shortest path from v1 to v3
 assert ssspRes.distance(v3) == 4.3;
 assert ssspRes.getPath(v3).equals(IntList.of(e1, e2));
 System.out.println("Distance from v1 to v3 is: " + ssspRes.distance(v3));
 System.out.println("The shortest path from v1 to v3 is:");
 for (int e : ssspRes.getPath(v3)) {
 	int 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.Result`	A result object for the `ShortestPathSingleSource` problem.

Method Summary

All Methods Static Methods Instance Methods Abstract Methods Default Methods
Modifier and Type	Method	Description
`default ShortestPathSingleSource.Result`	`computeCardinalityShortestPaths(Graph g, int source)`	Compute the cardinality shortest paths from a source to any other vertex in a graph.
`ShortestPathSingleSource.Result`	`computeShortestPaths(Graph g, WeightFunction w, int 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.

- Method Detail
  - computeShortestPaths
```
ShortestPathSingleSource.Result computeShortestPaths(Graph g,
                                                     WeightFunction w,
                                                     int 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.
    
    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
  - computeCardinalityShortestPaths
```
default ShortestPathSingleSource.Result computeCardinalityShortestPaths(Graph g,
                                                                        int source)
```
    Compute the cardinality shortest paths from a source to any other vertex in a graph.
    The cardinality length of a path is the number of edges in it. The cardinality shortest path from a source vertex to some other vertex is the path with the minimum number of edges.
    
    Parameters:
    
    g - a graph
    
    source - a source vertex
    
    Returns:
    
    a result object containing the distances and cardinality shortest paths from the source to any other vertex
  - newBuilder
```
static ShortestPathSingleSource.Builder newBuilder()
```
    Create a new single source shortest path algorithm builder.
    This is the recommended way to instantiate a new ShortestPathSingleSource object.
    
    Returns:
    
    a new builder that can build ShortestPathSingleSource objects

Interface ShortestPathSingleSource

Nested Class Summary

Method Summary

Method Detail

computeShortestPaths

computeCardinalityShortestPaths

newBuilder