Font Size: a A A

Analysis And Research On Algorithm For All Vertices-constrained Shortest Paths

Posted on:2009-05-11Degree:MasterType:Thesis
Country:ChinaCandidate:W Q WangFull Text:PDF
GTID:2178360242466432Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
K-nodes shortest path involves many domains, which is significant for traffic engineering, communication system, and so on. This algorithm is directed at the deficiency, and solve the problem on all shortest path with vertices-constrained. But in practice, the shortest path maybe is not the only one that is cared about. Also the second shortest path or the third shortest path are be cared about, and we call them generalized shortest paths. So this problem is also solved in the paper.This dissertation analyses the sense and status quo of the shortest path. Then introduce basic knowledge on graph and shortest path problem. Normal algorithms for shortest path are given and some algorithms related shortest paths are given too.Chapter 3 is the important one in this paper. First, a basic algorithm called BCSP algorithm is put forward. BCSP uses algorithm bfs and products spanning tree. Then all shortest paths are producted according to the spanning tree. But its time complexity is complex that is (?) (n is the number of vertices in a graph, k is the constrained number of vertices, c is the number of nodes on each level). Then algorithm ICSP is given out to improve its time complexity. ICSP uses inverse adjacency list, flag-array and point. It marks the list of the effected nodes based on the shortest path while other algorithms are concerned about only one node. And its time complexity is max {0((k-2)*w), 0(k*sh(G, i, j))} ( w is the number of arc in a graph, sh (G, i, j) is the number of shortest paths) that is better than algorithm BCSP. But in practice, the shortest path maybe is not the only one that is cared about. Also the second shortest path or the third shortest path are be cared about, and we call them generalized shortest paths. The algorithm GCSP is given to solve this problem. Algorithm GCSP bases on the algorithm ICSP, and it uses backtrack-algorithm to get all the generalized shortest paths, and its time complexity is 0(k~2* (sh(G, i, j) + (sh2(G, i, j))~2)( sh2(G, i, j) is the number of general shortest paths whose vertices are constrained).In chapter 4, we design a traffic model and conduct simulation studies to evaluate our algorithm and strategies. And we see the efficiency of this algorithm is high.
Keywords/Search Tags:inverse adjacency list, constrain, shortest path, spanning tree, general shortest path
PDF Full Text Request
Related items