A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time

DOI10.1007/s10878-012-9550-3zbMath1268.90072OpenAlexW2033646167MaRDI QIDQ1944395

Tadao Takaoka

Publication date: 25 March 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9550-3

zbMATH Keywords

algorithmpriority queueall pairs shortest pathsexpected time

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (1)

A Forward-Backward Single-Source Shortest Paths Algorithm

Cites Work

• A new approach to all-pairs shortest paths on real-weighted graphs
• On the Shortest Route Through a Network
• An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
• More algorithms for all-pairs shortest paths in weighted graphs
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time