File AllPairsShortestPaths.h

↰ Parent directory (ADS/graph)

The shortest paths between all the pairs of nodes, section 13.5: with the nodes v_0 , … , v_{n-1}, a path is k-bound if it passes through no node of { v_k , … , v_{n-1} } but its ends, and the least cost of the k-bound paths from u to v is.

Definition (ADS/graph/AllPairsShortestPaths.h)

Detailed Description

:math:`[
d^k[ u ][ v ] = min{ d^{k-1}[ u ][ v ] , d^{k-1}[ u ][ k - 1 ] +

d^{k-1}[ k - 1 ][ v ] } ,

` from :math:` d^0 ` the costs of the edges, 0 on the diagonal and :math:` +infty ` elsewhere, with p[ u ][ v ] the predecessor of v on the path from u. floydWarshall() overwrites d and p for k = 1 , … , n, Theta( n^3 ) time and Theta( n^2 ) space, with costs of any sign; there is a negative cycle through u if and only if d[ u ][ u ] < 0, and then negativeCycle is true. The row u of p is the tree of the shortest paths from u, as a vector of parents. The matrices have bound() rows, and those of a deleted node, its column and its place on the diagonal too, stay at :math:` +infty ` and NIL.

addEdge() updates d and p after the insertion of an edge ( a , b ) of cost w in O( n^2 ), since a path that improves goes through it once: :math:` d[ u ][ v ] = min{ d[ u ][ v ] , d[ u ][ a ] + w + d[ b ][ v ] } `, which needs that the edge closes no negative cycle, i.e., that w + d[ b ][ a ] >= 0 (exercise 13.5). A deletion has no such update: the paths that used the edge may need any other one.

The contracts [see File Contract.h]: addEdge() needs two distinct nodes of the matrix and an edge that closes no negative cycle; at the level of the audits, the distances found are closed under the triangle inequality, bounded by the costs of the edges, and their predecessors realize them, unless there is a negative cycle. The functions are defined in AllPairsShortestPaths.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 13.5, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Floyd, Algorithm 97: Shortest path, Communications of the ACM 5(6), 345, 1962, doi:10.1145/367766.368168

  2. Warshall, A theorem on Boolean matrices, Journal of the ACM 9(1), 11-12, 1962, doi:10.1145/321105.321107

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions