Defined in File FloydWarshall.hpp
public NetworKit::Algorithm (Class Algorithm)
Computes all-pairs shortest paths using the Floyd-Warshall algorithm.
This algorithm finds the shortest paths between all node pairs in a weighted graph, supporting both directed and undirected graphs. It correctly handles negative edge weights and detects negative cycles. If multiple shortest paths exist, it returns one with the fewest nodes.
The algorithm has a time complexity of O(n³), making it suitable for small to medium-sized graphs.
Public Types
Public Functions
Initializes the Floyd-Warshall algorithm for a given graph.
The input graph must be weighted and may be either directed or undirected.
G – The graph on which shortest paths will be computed.
Runs the Floyd-Warshall algorithm.
Computes shortest path distances and reconstructs paths between all node pairs. Also identifies nodes involved in negative cycles.
Returns the shortest distance between two nodes.
If no path exists, returns std::numeric_limits<edgeweight>::max().
source – The starting node.
target – The destination node.
The shortest path distance from source to target.
Checks whether a node is part of a negative cycle.
A node is considered part of a negative cycle if its shortest path distance to itself is negative.
u – The node to check.
true if the node is in a negative cycle, otherwise false.
Retrieves the shortest path between two nodes.
Returns a sequence of nodes representing the shortest path from source to target. If no path exists, returns an empty vector.
If multiple shortest paths exist with the same total distance, the function returns the one with the fewest nodes.
source – The starting node.
target – The destination node.
A vector of nodes forming the shortest path.
Returns the full all-pairs distance matrix.
The returned object is a reference to internal storage. Do not modify it directly; call run() again if the graph changes.
A matrix where entry [u][v] is the shortest distance from u to v.