Faster algorithms for the shortest path problem

DOI10.1145/77600.77615zbMath0696.68046DBLPjournals/jacm/AhujaMOT90OpenAlexW2160365857WikidataQ55923156 ScholiaQ55923156MaRDI QIDQ3474275

James B. Orlin, Kurt Mehlhorn, Ravindra K. Ahuja, Robert Endre Tarjan

Publication date: 1990

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/47994

zbMATH Keywords

networkshortest pathpriority queueheap

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (64)

Trans-dichotomous algorithms for minimum spanning trees and shortest paths ⋮ Parameter-free sampled fictitious play for solving deterministic dynamic programming problems ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Complexity results for the linear time-cost tradeoff problem with multiple milestones and completely ordered jobs ⋮ Unnamed Item ⋮ All-pairs shortest paths and the essential subgraph ⋮ Rank-Sensitive Priority Queues ⋮ On the exponent of all pairs shortest path problem ⋮ Analysis of FPTASes for the multi-objective shortest path problem ⋮ On fast planning of suboptimal paths amidst polygonal obstacles in plane ⋮ An improved Dijkstra's shortest path algorithm for sparse network ⋮ OUTSOURCING DECISIONS IN m-MACHINE PERMUTATION FLOW SHOP SCHEDULING PROBLEMS WITH MACHINE-DEPENDENT PROCESSING TIMES ⋮ The k most vital arcs in the shortest path problem ⋮ Analyzing the reachability problem in choice networks ⋮ Shortest paths algorithms: Theory and experimental evaluation ⋮ The suffix tree of a tree and minimizing sequential transducers ⋮ Two-level heaps: a new priority queue structure with applications to the single source shortest path problem ⋮ Coordination mechanisms for parallel machine scheduling ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Efficiently Listing Bounded Length st-Paths ⋮ Sharing information for the all pairs shortest path problem ⋮ A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work ⋮ Shortest paths in random weighted graphs ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Reachability in choice networks ⋮ Minimizing makespan in an ordered flow shop with machine-dependent processing times ⋮ A linear time-cost tradeoff problem with multiple milestones under a comb graph ⋮ Two-Machine and Two-Agent Flow Shop with Special Processing Times Structures ⋮ Two-machine flow shop scheduling problem with an outsourcing option ⋮ A sequential algorithm for finding a maximum weightK-independent set on interval graphs ⋮ A just-in-time scheduling problem with two competing agents ⋮ On graphs preserving rectilinear shortest paths in the presence of obstacles ⋮ Computing the optimal IO sequences of a protocol in polynomial time ⋮ Shortest path algorithms: A computational study with the C programming language ⋮ A double scaling algorithm for the constrained maximum flow problem ⋮ TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION ⋮ Two-agent parallel machine scheduling with a restricted number of overlapped reserved tasks ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ A faster polynomial algorithm for the constrained maximum flow problem ⋮ An optimal algorithm for the period of a strongly connected digraph ⋮ A faster algorithm for the single source shortest path problem with few distinct positive lengths ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ On sorting, heaps, and minimum spanning trees ⋮ Faster shortest-path algorithms for planar graphs ⋮ Complexity of single machine scheduling subject to nonnegative inventory constraints ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Integer priority queues with decrease key in constant time and the single source shortest paths problem ⋮ On the shortest path problem with negative cost cycles ⋮ Weighted fusion graphs: Merging properties and watersheds ⋮ Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty ⋮ An efficient implementation of an algorithm for findingK shortest simple paths ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS ⋮ JUST-IN-TIME SCHEDULING UNDER SCENARIO-BASED UNCERTAINTY ⋮ Minimization algorithms for sequential transducers ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ Finding the k Shortest Paths ⋮ Paths and trails in edge-colored weighted graphs ⋮ Semi-dynamic breadth-first search in digraphs ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ Theory of 2-3 heaps ⋮ A linear time algorithm for the maximum capacity path problem ⋮ Structural properties of NFAs and growth rates of nondeterminism measures

This page was built for publication: Faster algorithms for the shortest path problem