Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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.