File ShortestPaths.h

↰ Parent directory (ADS/graph)

The shortest paths of chapter 11 from a node r of an oriented GRAPH whose edges have a cost w( u , v ) [see File Graph.h].

Definition (ADS/graph/ShortestPaths.h)

Detailed Description

A feasible solution is a tree T rooted in r, each node v at distance :math:` d_v ` from r in T; by the theorem of Bellman (Teorema 11.1) T is optimal if and only if :math:`[

d_v = d_u + w( u , v ) quad forall ( u , v ) in T , qquad d_u + w( u , v ) geq d_v quad forall ( u , v ) in E .

` The prototype (section 11.2) starts from d = 0 in r and :math:` + infty ` elsewhere and, while an edge violates the condition, sets :math:` d_v = d_u + w( u , v ) ` and makes u the parent of v; a structure S holds the nodes whose edges must be checked. Its kind gives the algorithm [see Frontier]:

  • LIST, a priority queue on an unsorted list: Dijkstra (1959), each node extracted once if the costs are not negative, :math:` O( n^2 ) `;

  • HEAP, a priority queue on a binary heap: Johnson (1977), :math:` O( m log n ) `;

  • FIBONACCI, a priority queue on a Fibonacci heap: Fredman and Tarjan (1987), :math:` O( m + n log n ) `;

  • QUEUE: Bellman-Ford-Moore, a node extracted at most n times even with negative costs, :math:` O( n m ) `, and a negative cycle reachable from r is detected when a node is extracted more than n times (exercise 11.2); with the other frontiers there must be no negative cycle;

  • STACK: superpolynomial in the worst case (section 11.7);

  • DEQUE: Pape-D’Esopo (section 11.8), a node at the tail of S the first time and at its head afterwards, superpolynomial in the worst case and the fastest in practice on road networks.

With a priority queue a node already in S has its priority decreased (the line (4) of the book); in the code of the book the new distance and parent of v are written in both branches of that test. The structure S is a type [see PrototypeFrontier]: shortestPaths() with a Frontier runs the prototype on the six structures of the book, and the prototype runs as well on any priority queue of section 10.1 [see PriorityFrontier], queue, stack or deque of another library; with the priorities :math:` ( d_v , v ) ` the ties are broken by the names of the nodes, and every priority queue extracts the same nodes in the same order, so that the counts of a run [see FrontierCounts] measure the same work on any of them. Without negative cycles every frontier gives the shortest paths; with negative costs the priority queues are still correct but may extract a node more than once. dagShortestPaths() scans an acyclic graph in topological order, :math:` O( n + m ) ` whatever the signs of the costs. The distances are sums in D, not checked for overflow: the cost of every path from r must stay strictly between -infinity< D >() and infinity< D >(), and a node at distance infinity< D >() counts as unreachable.

The contracts [see File Contract.h]: r is a node; with a frontier other than QUEUE no negative cycle is reachable from r, and dagShortestPaths() needs an acyclic graph, both checked at the level of the audits (the first by Bellman-Ford, O( n m )); the tree found satisfies the conditions of Bellman unless a negative cycle was found, which isShortestPathTree() checks. The functions are defined in ShortestPaths.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 11, https://algoritmicamente.it/materiali/libro/capitoli/cap11.pdf

  1. Bellman, On a routing problem, Quarterly of Applied Mathematics 16(1), 87-90, 1958, doi:10.1090/qam/102435

    1. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 269-271, 1959, doi:10.1007/BF01386390

    1. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM 34(3), 596-615, 1987, doi:10.1145/28869.28874

    1. Ford Jr., Network flow theory, RAND Corporation paper P-923, 1956

    1. Moore, The shortest path through a maze, Proceedings of an International Symposium on the Theory of Switching, Part II, Harvard University Press, 285-292, 1959

    1. Johnson, Efficient algorithms for shortest paths in sparse networks, Journal of the ACM 24(1), 1-13, 1977, doi:10.1145/321992.321993

  1. Pape, Implementation and efficiency of Moore-algorithms for the shortest route problem, Mathematical Programming 7, 212-222, 1974, doi:10.1007/BF01585517

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Enums

Functions