An efficient algorithm for computing least cost paths with turn constraints

被引：21

作者：

Boroujerdi, A ^{[1
]}

Uhlmann, J ^{[1
]}

机构：

[1] USN, Res Lab, Div Informat Technol, Washington, DC 20375 USA

来源：

INFORMATION PROCESSING LETTERS | 1998年 / 67卷 / 06期

关键词：

Dijkstra's algorithm; shortest paths; least cost paths; range searching; routing; turn constraints; computational complexity;

D O I：

10.1016/S0020-0190(98)00134-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

An algorithm is presented for computing least cost paths under turn angle constraints. The approach is almost as efficient as Dijkstra's algorithm for unconstrained least cost paths. Specifically, if a graph representation of a two- or three-dimensional routing problem contains \V\ vertices and \E\ edges, then our algorithm scales as O(\E\ log \V\) versus the O(\V\ log \V\ + \E\) complexity for the most efficient implementation of Dijkstra's algorithm. This result is substantially better than O(\E\\V\) algorithms for the more general problem of routing with turn penalties, which cannot be applied to large scale graphs. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

引用

页码：317 / 321

页数：5