Shortest path queries in planar graphs
Shortest path queries in planar graphs
复制标题
平面图中的最短路径查询
DOI：
10.1145/335305.335359
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Jinhui Xu
中科院分区：
文献类型：
--
作者：
D. Chen;Jinhui Xu
处理图中最短路径查询的问题出现在智能交通系统（ITS）、地理信息系统（GIS）和机器人等应用领域中。在本文中，我们提出了一种有效的算法解决方案，用于处理具有非负边权重的无向平面图中的最短路径查询。以前针对平面图上的这个问题的算法都在查询时间和解决方案所使用的数据结构空间之间进行权衡。在最坏情况下，n 顶点平面图 G 上先前已知的权衡是路径长度查询的 O(v/-r) 时间和报告实际最短路径的 O(v/-r + L) 时间，数据结构为 O(n2/x/~) 空间，其中 r 是整数参数，1 < r _< n，L 是输出最短路径上的边数。我们提出了一种称为框架搜索的新方案，它以一种新颖的方式利用图平面性。通过该方案，我们构建了 O(n + pv/-r + p2/r) 空间的改进数据结构（在 O(n + p2/v/~ + pr 3/4) 时间内），其中 p 是 G 平面嵌入的面覆盖的最小基数，其中 1 < p < O(n)，r 是整数参数，1 < r < p。这种数据结构使我们能够在 O(v/-rlog r + a(n)) 时间内处理每个长度查询，并在额外的 O(L) 时间内报告实际的最短路径，其中 a(n) 是阿克曼函数的反函数。在最坏的情况下，如果使用相同的空间量，我们的方法会将先前的最佳查询时间减少多达 O(n 1/4) 倍。我们的技术还可以应用于改进先前针对平面上的一些几何最短路径问题的查询算法。
The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v/-r) t ime for a pa th length query and O(v/-r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2/x/~) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv/-r + p2/r) space (in O(n + p2/v/~ + pr 3/4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v/-rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1/4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane.