共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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+nr2) to O(mn+r3). 相似文献
4.
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
3). On the randomized CRCW PRAM we are able to achieve time complexityO(n
3/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. 相似文献
5.
Yijie Han 《Information Processing Letters》2004,91(5):245-250
We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n3(loglogn/logn)5/7) time. This improves the best previous result which runs in O(n3(loglogn/logn)1/2) time. 相似文献
6.
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. 相似文献
7.
Shortest paths between shortest paths 总被引:1,自引:0,他引:1
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. 相似文献
8.
改进的Dijkstra最短路径算法及其应用研究 总被引:5,自引:1,他引:5
求最短路径是一个应用很广泛的问题。求最短路径的算法有很多,公认较好的算法是Dijkstra标号法。但实验结果表明,Dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的,会陷入死循环;②没有涉及最短路径上顶点的邻接点(特指前面的相邻点)问题;③没有涉及多个顶点同时获得p标号的问题。针对上述问题,对标号法进行了改进。算法实验表明,改进的标号法能够有效解决上述问题。在上述工作的基础上,开发了"北京市道路最优路线选择系统",以提供起点和终点之间的最优路线,帮助用户选择出行路线,使市民能够避过交通最拥堵的路段,节约出行时间。 相似文献
9.
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
2
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. 相似文献
10.
Nattapat Attiratanasunthron 《Information Processing Letters》2008,105(3):88-92
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. 相似文献
11.
在深入分析传统Dijkstra算法的基础上,提出了利用基于k叉堆的优先级队列对算法进行改进的思想,并对3种可合并替进行了比较,从理论上证明了四叉堆在k叉堆中的最优性,设计了基于四叉堆优先级队列及逆领接表,顾及路段方向阻抗的改进型Dijkstra最短径算法,将Dijstra算法复杂度降为O(nlogn)。 相似文献
12.
在深入分析传统Dijkstra算法的基础上,提出了利用基于k 叉堆的优先级队列对算法进行改进的思想,并对3 种可合并堆进行了比较,从理论上证明了四叉堆在k 叉堆中的最优性,设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Dijkstra最短路径算法,将Dijkstra 算法复杂度降为O(nlogn)。针对GIS-T应用系统的动态特征,提出了Dijkstra 算法的逆序计算方法,通过构造逆序最短路径树,使算法更具灵活性和实用性 相似文献
13.
地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Dijkstra算法的基础上,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了该算法的分析效率。讨论了地理网络数据的组织结构和最短路径的具体实现过程,并引入了相关概念,并引入了相关概念,通过具体案例分析表明,改进算法在提高网络系统空间分析效率方面是可行的。 相似文献
14.
Yijie Han 《Algorithmica》2008,51(4):428-434
We present an O(n
3(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
3/log n) time.
Research supported in part by NSF grant 0310245. 相似文献
15.
一种新型最短路径搜索算法的研究 总被引:5,自引:3,他引:2
在深入分析Dijksdtra算法的基础上,考虑到图节点之间的拓扑关系以及Dijksdtra算法在计算节点权值时,与已着色节点不相关节点权值存在∞(即该节点不可见),文章提出了盲目区域最短路径搜索算法,由分析可知计算量大为减少,算法更优。 相似文献
16.
Vadim Lozin 《Information Processing Letters》2003,88(4):167-171
Many NP-hard graph problems remain difficult on Pk-free graphs for certain values of k. Our goal is to distinguish subclasses of Pk-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 (Pk,K1,n)-free graphs for any positive integers k and n, thereby generalizing several known results. 相似文献
17.
In an undirected graph, paths P1,P2,…,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 {s1,t1},…,{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. 相似文献
18.
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. 相似文献
19.