Shortest paths in euclidean graphs

We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph withV vertices andE edges is shown to beO(V) as compared withO(E +V logV) required by the classical algorithm due to Dijkstra.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

Solving shortest paths efficiently on nearly acyclic directed graphs

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr²) to O(mn+r³).     

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexityO(f(n)/p+I(n)logn) on the PRAM usingp processors, whereI(n) is logn on the EREW PRAM, log logn on the CCRW PRAM,f(n) iso(n ³). On the randomized CRCW PRAM we are able to achieve time complexityO(n ³/p+logn) usingp processors. A preliminary version of this paper was presented at the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992. Support by NSF Grant CCR 90-20690 and PSC CUNY Awards #661340 and #662478.     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Shortest paths in simple polygons with polygon-meet constraints

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons.     

Shortest paths between shortest paths

We study the following problem on reconfiguring shortest paths in graphs: Given two shortest s-t paths, what is the minimum number of steps required to transform one into the other, where each intermediate path must also be a shortest s-t path and must differ from the previous one by only one vertex. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length.     

改进的Dijkstra最短路径算法及其应用研究

求最短路径是一个应用很广泛的问题。求最短路径的算法有很多,公认较好的算法是Dijkstra标号法。但实验结果表明,Dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的,会陷入死循环;②没有涉及最短路径上顶点的邻接点(特指前面的相邻点)问题;③没有涉及多个顶点同时获得p标号的问题。针对上述问题,对标号法进行了改进。算法实验表明,改进的标号法能够有效解决上述问题。在上述工作的基础上,开发了"北京市道路最优路线选择系统",以提供起点和终点之间的最优路线,帮助用户选择出行路线,使市民能够避过交通最拥堵的路段,节约出行时间。     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

A running time analysis of an Ant Colony Optimization algorithm for shortest paths in directed acyclic graphs

In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is for graphs with n nodes and m edges, where ρ is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if ρ=O(n−1−ε) for any ε>0.     

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上,提出了利用基于ｋ叉堆的优先级队列对算法进行改进的思想,并对３种可合并替进行了比较,从理论上证明了四叉堆在ｋ叉堆中的最优性,设计了基于四叉堆优先级队列及逆领接表,顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短径算法,将Ｄｉｊｓｔｒａ算法复杂度降为Ｏ（ｎｌｏｇｎ）。     

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上,提出了利用基于ｋ 叉堆的优先级队列对算法进行改进的思想,并对３ 种可合并堆进行了比较,从理论上证明了四叉堆在ｋ 叉堆中的最优性,设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短路径算法,将Ｄｉｊｋｓｔｒａ 算法复杂度降为Ｏ（ｎｌｏｇｎ）。针对ＧＩＳ－Ｔ应用系统的动态特征,提出了Ｄｉｊｋｓｔｒａ 算法的逆序计算方法,通过构造逆序最短路径树,使算法更具灵活性和实用性     

GIS中使用改进的Dijkstra算法实现最短路径的计算

地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Ｄｉｊｋｓｔｒａ算法的基础上,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了该算法的分析效率。讨论了地理网络数据的组织结构和最短路径的具体实现过程,并引入了相关概念,并引入了相关概念,通过具体案例分析表明,改进算法在提高网络系统空间分析效率方面是可行的。     

An O(n 3(log log n/log n)5/4) Time Algorithm for All Pairs Shortest Path

We present an O(n ³(log log n/log n)^5/4) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n ³/log n) time. Research supported in part by NSF grant 0310245.     

一种新型最短路径搜索算法的研究

在深入分析Dijksdtra算法的基础上,考虑到图节点之间的拓扑关系以及Dijksdtra算法在计算节点权值时,与已着色节点不相关节点权值存在∞（即该节点不可见）,文章提出了盲目区域最短路径搜索算法,由分析可知计算量大为减少,算法更优。     

Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

Finding multiple induced disjoint paths in general graphs

In an undirected graph, paths P₁,P₂,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s₁,t₁},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

多链路权值增大的动态最短路径算法

动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点更新次数和更高的时间效率。     

基于蚁群算法的拥堵交通最短路径研究

针对当前交通网络在路径选择研究中,存在只考虑静态交通网络的路径选择的问题,提出了利用蚁群算法的拥堵交通网络的最短路径算法,建立了采用Petri网的交通网络模型,运用蚁群算法对静态交通网络进行了最短路径求解,并加入天气状况、道路容量等动量建立动态交通网络.运用层次分析法并结合Petri网对交通拓扑图进行了最短路径的探索并进行了对比分析.研究结果表明在道路拥挤的情况下,动态交通网络下的路径算法可以为出行者找到更快捷方便的路线.