L1 cheapest paths in "Fjord Scenery.".
- Resource Type
- Article
- Authors
- Kulpa, W.; Pordzik, M.; Socha, L.; Turzanski, M.
- Source
- European Journal of Operational Research. Mar2005, Vol. 161 Issue 3, p736-753. 18p. 9 Diagrams, 2 Charts, 1 Graph.
- Subject
- *ALGORITHMS
*MATHEMATICAL optimization
*OPERATIONS research
*COMPUTER systems
COMBINATORICS
- Language
- ISSN
- 0377-2217
We show a simple proof of the existence of a path on the "border of water and rocks" based on combinatorial induction procedure and we present an algorithm for computing L1 shortest path in "Fjord Scenery". The proposed algorithm is a version of the Dijkstra technique adapted to a rectangle map with a square network. A few pre- processing modifications of the algorithm following from the combinatorial procedure are included. The validity of this approach is shown by numerical calculations for an example. [ABSTRACT FROM AUTHOR]