Shortest Paths

Algorithms for computing shortest paths in graphs (including single-source and all-pairs). More...

Classes
class	ogdf::AStarSearch< T >
	A-Star informed search algorithm. More...
class	ogdf::Dijkstra< T, H >
	Dijkstra's single source shortest path algorithm. More...
class	ogdf::ShortestPathWithBFM
	Computes single-source shortest-paths with Bellman-Ford-Moore's algorithm. More...

Functions
template<typename TCost >
void	ogdf::bfs_SPAP (const Graph &G, NodeArray< NodeArray< TCost >> &distance, TCost edgeCosts)
	Computes all-pairs shortest paths in G using breadth-first serach (BFS). More...
template<typename TCost >
void	ogdf::bfs_SPSS (node s, const Graph &G, NodeArray< TCost > &distanceArray, TCost edgeCosts)
	Computes single-source shortest paths from s in G using breadth-first search (BFS). More...
template<typename TCost >
void	ogdf::dijkstra_SPAP (const Graph &G, NodeArray< NodeArray< TCost >> &shortestPathMatrix, const EdgeArray< TCost > &edgeCosts)
	Computes all-pairs shortest paths in graph G using Dijkstra's algorithm. More...
template<typename TCost >
double	ogdf::dijkstra_SPAP (const GraphAttributes &GA, NodeArray< NodeArray< TCost >> &shortestPathMatrix)
	Computes all-pairs shortest paths in GA using Dijkstra's algorithm. More...
template<typename TCost >
void	ogdf::dijkstra_SPSS (node s, const Graph &G, NodeArray< TCost > &shortestPathMatrix, const EdgeArray< TCost > &edgeCosts)
	Computes single-source shortest paths from node s in G using Disjkstra's algorithm. More...
template<typename TCost >
void	ogdf::floydWarshall_SPAP (NodeArray< NodeArray< TCost >> &shortestPathMatrix, const Graph &G)
	Computes all-pairs shortest paths in graph G using Floyd-Warshall's algorithm. More...

Detailed Description

Algorithms for computing shortest paths in graphs (including single-source and all-pairs).

Function Documentation

bfs_SPAP()

template<typename TCost >

void ogdf::bfs_SPAP	(	const Graph &	G,
		NodeArray< NodeArray< TCost >> &	distance,
		TCost	edgeCosts
	)

Computes all-pairs shortest paths in G using breadth-first serach (BFS).

The cost of each edge are edgeCost and the result is stored in distance.

Definition at line 50 of file ShortestPathAlgorithms.h.

bfs_SPSS()

template<typename TCost >

void ogdf::bfs_SPSS	(	node	s,
		const Graph &	G,
		NodeArray< TCost > &	distanceArray,
		TCost	edgeCosts
	)

Computes single-source shortest paths from s in G using breadth-first search (BFS).

The cost of each edge are edgeCost and the result is stored in distanceArray.

Definition at line 63 of file ShortestPathAlgorithms.h.

dijkstra_SPAP() [1/2]

template<typename TCost >

void ogdf::dijkstra_SPAP	(	const Graph &	G,
		NodeArray< NodeArray< TCost >> &	shortestPathMatrix,
		const EdgeArray< TCost > &	edgeCosts
	)

Computes all-pairs shortest paths in graph G using Dijkstra's algorithm.

The cost of an edge are given by edgeCosts and the result is stored in shortestPathMatrix.

Definition at line 112 of file ShortestPathAlgorithms.h.

dijkstra_SPAP() [2/2]

template<typename TCost >

double ogdf::dijkstra_SPAP	(	const GraphAttributes &	GA,
		NodeArray< NodeArray< TCost >> &	shortestPathMatrix
	)

Computes all-pairs shortest paths in GA using Dijkstra's algorithm.

The cost of an edge e are given by GA.doubleWeight(e) and the result is stored in shortestPathMatrix.

Returns

returns the average edge cost

Definition at line 93 of file ShortestPathAlgorithms.h.

dijkstra_SPSS()

template<typename TCost >

void ogdf::dijkstra_SPSS	(	node	s,
		const Graph &	G,
		NodeArray< TCost > &	shortestPathMatrix,
		const EdgeArray< TCost > &	edgeCosts
	)

Computes single-source shortest paths from node s in G using Disjkstra's algorithm.

The cost of an edge are given by edgeCosts and the result is stored in shortestPathMatrix. Note this algorithm equals Dijkstra<T>::call, though it does not compute the predecessors on the path and is not inlined.

Definition at line 128 of file ShortestPathAlgorithms.h.

floydWarshall_SPAP()

template<typename TCost >

void ogdf::floydWarshall_SPAP	(	NodeArray< NodeArray< TCost >> &	shortestPathMatrix,
		const Graph &	G
	)

Computes all-pairs shortest paths in graph G using Floyd-Warshall's algorithm.

Note that the shortestPathMatrix has to be initialized and all entries must be positive. The costs of non-adjacent nodes should be set to std::numeric_limits<TCost>::infinity().

Definition at line 143 of file ShortestPathAlgorithms.h.