Package com.jgalgo.alg.shortestpath

Class ShortestPathSingleSourceAbstract

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract

All Implemented Interfaces:

ShortestPathSingleSource

Direct Known Subclasses:

ShortestPathSingleSourceBellmanFord, ShortestPathSingleSourceCardinality, ShortestPathSingleSourceDag, ShortestPathSingleSourceDial, ShortestPathSingleSourceDijkstra, ShortestPathSingleSourceGoldberg

public abstract class ShortestPathSingleSourceAbstract
extends Object
implements ShortestPathSingleSource

Abstract class for computing shortest path from a single source in graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.shortestpath.ShortestPathSingleSource

ShortestPathSingleSource.Builder, ShortestPathSingleSource.IResult, ShortestPathSingleSource.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
ShortestPathSingleSourceAbstract()	Default constructor.

Method Summary

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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ShortestPathSingleSourceAbstract

public ShortestPathSingleSourceAbstract()

Default constructor.

Method Detail

computeShortestPaths

public <V,E> ShortestPathSingleSource.Result<V,E> computeShortestPaths(Graph<V,E> g,
                                                                                   WeightFunction<E> w,
                                                                                   V source)

Description copied from interface: ShortestPathSingleSource

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.

Specified by:

computeShortestPaths in interface ShortestPathSingleSource

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