Shortest path algorithms for nearly acyclic directed graphs

DOI10.1016/S0304-3975(97)00292-2zbMath0913.68085MaRDI QIDQ1274325

Tadao Takaoka

Publication date: 12 January 1999

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

zbMATH Keywords

algorithmpriority queueshortest pathsDijkstra's algorithmacyclic graphnearly acyclic graphFibonacci heap

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (3)

Solving shortest paths efficiently on nearly acyclic directed graphs ⋮ Sharing information for the all pairs shortest path problem ⋮ Improved shortest path algorithms for nearly acyclic graphs

Uses Software

• Algorithm 97

Cites Work

• A note on two problems in connexion with graphs
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Fibonacci heaps and their uses in improved network optimization algorithms
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item

This page was built for publication: Shortest path algorithms for nearly acyclic directed graphs