Package com.jgalgo.alg

Interface ShortestPathSingleSource

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.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 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

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

Modifier and Type	Method	Description
static ShortestPathSingleSource.Builder	builder()	Create a new single source shortest path algorithm builder.
<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	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

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

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

builder

static ShortestPathSingleSource.Builder builder()

Create a new single source shortest path algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build ShortestPathSingleSource objects