An algorithm for finding shortest paths in a maze

DOI10.1080/02331938608843123MaRDI QIDQ3724109zbMATH OpenOpenAlexFDO

Authors Boris V. Cherkassky

Publication date 1986

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331938608843123

zbMATH Keywords

equivalent networkrunning-timeshortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• Shortest paths in the plane with convex polygonal obstacles
• Shortest paths in the plane with polygonal obstacles
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Paths through a maze of rectangles
• Planar rectilinear shortest path computation using corridors

Cited in

(7)

• Time-efficient maze routing algorithms on reconfigurable mesh architectures
• Characterizing the shortest path of an object among obstacles
• An approximate path finding algorithm for bridging special obstacles
• Consequence programming: the algorithm ``at subgoal go back
• A Maze Routing Algorithm Based on Two Dimensional Cellular Automata
• Paths through a maze of rectangles
• Un algoritmo estocástico para resolver laberintos

This page was built for publication: An algorithm for finding shortest paths in a maze

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