Shortest‐path methods: Complexity, interrelations and new propositions

DOI10.1002/net.3230140206zbMath0583.90103OpenAlexW2062266989MaRDI QIDQ3706872

Stefano Pallottino

Publication date: 1984

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230140206

zbMATH Keywords

computational complexityunified approachshortest-path problemsfinite sequence of partial graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items (18)

A heuristic improvement of the Bellman-Ford algorithm ⋮ Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm ⋮ Intelligent transportation systems -- Enabling technologies ⋮ Dynamic traffic assignment: Considerations on some deterministic modelling approaches ⋮ A computational study of efficient shortest path algorithms ⋮ Shortest paths algorithms: Theory and experimental evaluation ⋮ A strategic oscillation simheuristic for the time capacitated arc routing problem with stochastic demands ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location ⋮ Least possible time paths in stochastic, time-varying networks. ⋮ An efficient label setting/correcting shortest path algorithm ⋮ GNet: a generalized network model and its applications in qualitative spatial reasoning ⋮ A simplification of the double-sweep algorithm to solve the \(k\)-shortest path problem ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Stochastic task networks -- trading performance for stability ⋮ Multicriteria adaptive paths in stochastic, time-varying networks ⋮ An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays ⋮ Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm

Cites Work

• A Note on Dijkstra's Shortest Path Algorithm
• A Theorem on Boolean Matrices
• Unnamed Item

This page was built for publication: Shortest‐path methods: Complexity, interrelations and new propositions