On the optimality of Bellman-Ford-Moore shortest path algorithm

DOI10.1016/J.TCS.2016.03.014zbMATH Open1339.90327OpenAlexW2294351956MaRDI QIDQ266282FDOQ266282

Authors: Georg Schnitger, Stasys Jukna 

Publication date: 13 April 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.03.014

Recommendations

• A new algorithm for the shortest-path problem
• A lower bound for the shortest path problem
• Scaling Algorithms for the Shortest Paths Problem
• New Bounds on the Complexity of the Shortest Path Problem
• Shortest paths in almost acyclic graphs

zbMATH Keywords

dynamic programmingshortest pathslower boundsmatrix multiplicationtropical semiring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39)

Cites Work

• On a routing problem
• On maximal paths and circuits of graphs
• A Theorem on Boolean Matrices
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Lower bounds for tropical circuits and dynamic programs
• Formulas vs. circuits for small distance connectivity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reliable circuits using less reliable relays
• Some Theorems on Abstract Graphs

Cited In (6)

• Title not available (Why is that?)
• Improvement and experimental evaluation on classical Bellman-Ford algorithm
• Lower bounds for non-adaptive shortest path relaxation
• Title not available (Why is that?)
• Randomized Speedup of the Bellman–Ford Algorithm
• Hybrid Bellman-Ford-Dijkstra algorithm

Uses Software

• Algorithm 97

This page was built for publication: On the optimality of Bellman-Ford-Moore shortest path algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266282)