Finding The K Shortest Simple Paths: A New Algorithm And .
Finding the k Shortest Simple Paths:A New Algorithm and its ImplementationJohn Hershberger Matthew Maxel†AbstractWe describe a new algorithm to enumerate the kshortest simple (loopless) paths in a directed graph andreport on its implementation. Our algorithm is basedon a replacement paths algorithm proposed recentlyby Hershberger and Suri [7], and can yield a factorΘ(n) improvement for this problem. But there is acaveat: the fast replacement paths subroutine is knownto fail for some directed graphs. However, the failure iseasily detected, and so our k shortest paths algorithmoptimistically uses the fast subroutine, then switches toa slower but correct algorithm if a failure is detected.Thus the algorithm achieves its Θ(n) speed advantageonly when the optimism is justified. Our empiricalresults show that the replacement paths failure is arare phenomenon, and the new algorithm outperformsthe current best algorithms; the improvement can besubstantial in large graphs. For instance, on GISmap data with about 5000 nodes and 12000 edges,our algorithm is 4-8 times faster. In synthetic graphsmodeling wireless ad hoc networks, our algorithm isabout 20 times faster.1IntroductionThe k shortest paths problem is a natural and longstudied generalization of the shortest path problem, inwhich not one but several paths in increasing order oflength are sought. Given a directed graph G with nonnegative edge weights, a positive integer k, and twovertices s and t, the problem asks for the k shortestpaths from s to t in increasing order of length. Werequire that the paths be simple (loop free). SeeFigure 1 for an example illustrating the difference Mentor Graphics Corp,8005 SW Boeckman Road,Wilsonville, OR 97070, john hershberger@mentor.com.† Department of Computer Science, University of California,Santa Barbara, CA 93106.‡ Department of Computer Science, University of California,Santa Barbara, CA 93106, suri@cs.ucsb.edu. Supported in partby National Science Foundation grants CCR-9901958 and IIS0121562.Subhash Suri‡between the k shortest paths problem with and withoutthe simplicity constraint. (As the figure shows, evenin graphs with non-negative weights, although theshortest path is always simple, the subsequent pathscan have cycles.) The k shortest paths problemin which paths are not required to be simple turnsout to be significantly easier. An O(m kn log n)time algorithm for this problem has been known since1975 [3]; a recent improvement by Eppstein essentiallyachieves the optimal time of O(m n log n k)—thealgorithm computes an implicit representation of thepaths, from which each path can be output in O(n)additional time [2].g1010s1a111b11cd1e1t1110hFigure 1: The difference between simple and nonsimple k shortest paths. The three simple shortestpaths have lengths 6, 20 and 21, respectively. Withoutthe simplicity constraint, paths may use the cycles(a, b, a) and (d, e, d), giving shortest paths of lengths6, 8, 10.The problem of determining the k shortest simplepaths has proved to be more challenging. The problemwas originally examined by Hoffman and Pavley [10],but nearly all early attempts to solve it led to exponential time algorithms [16]. The best result knownto date is an algorithm by Yen [18, 19] (generalized by Lawler [12]), which using modern data structures can be implemented in O(kn(m n log n)) worstcase time. This algorithm essentially performs O(n)
single-source shortest path computations for each output path. In the case of undirected graphs, Katoh,Ibaraki, and Mine [11] improve Yen’s algorithm toO(k(m n log n)) time. While Yen’s asymptotic worstcase bound for enumerating k simple shortest paths in adirected graph remains unbeaten, several heuristic improvements to his algorithm have been proposed andimplemented, as have other algorithms with the sameworst-case bound. See for example [1, 6, 13, 14, 15].In this paper we propose a new algorithm to findthe k shortest simple paths in a directed graph. Ouralgorithm is based on the efficient replacement pathsalgorithm of Hershberger and Suri [7], which gives aΘ(n) speedup over the naı̈ve algorithm for replacementpaths. The efficient algorithm is known to fail for somedirected graphs [8]. However, the failure is easy to detect, and so our k shortest paths algorithm optimistically tries the fast replacement paths subroutine, thenswitches to a slower but correct algorithm if a failureoccurs.We have implemented our optimism-based k shortest paths algorithm, and our empirical results showthat the replacement paths algorithm almost alwayssucceeds—in our experiments, the replacement pathssubroutine failed less than 1% of the time. Thus, weobtain a speedup over Yen’s algorithm that is closeto the best-case linear speedup predicted by theory.The algorithm is never much worse than Yen’s, andon graphs where shortest paths have many edges, suchas those derived from GIS data or locally-connectedradio networks, the improvement is substantial. Forinstance, on GIS data representing road networks inthe United States, our algorithm is about 20% fasterfor paths from Washington, D.C., to New York (relatively close cities), and about 8 times faster for pathsfrom San Diego to Piercy, CA. Similarly, on syntheticmodels of wireless networks, our algorithm is 10 to 20times faster. Random graphs tend to have small diameters, but even on those graphs, our algorithm usuallyoutperforms Yen’s algorithm.The fact that Yen’s worst-case bound for directedgraphs remains unbeaten after 30 years raises the possibility that no better algorithm exists. Indeed, Hershberger, Suri, and Bhosle recently have shown thatin a slightly restricted version of the path comparisonmodel, the replacement pathsdirected problem in a graph has complexity Ω(m n), if m O(n n) [9].(Most known shortest path algorithms, including thoseby Dijkstra, Bellman-Ford and Floyd-Warshall, satisfythis model. The exceptions to this model are the matrix multiplication based algorithms by Fredman andothers [4, 17, 20].) The same lower bound constructionshows that any k simple shortest paths algorithm thatfinds the best candidate path for each possible branchpoint off previously chosen paths is also subject to thislower bound, even for k 2. All known algorithms forthe k simple shortest paths fall into this category.2Path Branching andEquivalence ClassesIn the k shortest paths problem we are given a directedgraph G (V, E), with n vertices and m edges. Eachedge e E has an associated non-negative weight c(e).A path in G is a sequence of edges, with the head ofeach edge connected to the tail of its successor at acommon vertex. A path is simple if all its vertices aredistinct. The total weight of a path in G is the sum ofthe weights of the edges on the path. The shortest pathbetween two vertices s and t, denoted by path(s, t), isthe path joining s to t, assuming one exists, that hasminimum weight. The weight of path(s, t) is denotedby d(s, t).We begin with an informal description of thealgorithm. Our algorithm generates k shortest paths inorder of increasing length. Suppose we have generatedthe first i shortest paths, namely, the set Πi {P1 , P2 , . . . , Pi }. Let Ri denote the set of remainingpaths that join s to t; this is the set of candidate pathsfor the remaining k i shortest paths. In order to findthe next shortest path in Ri efficiently, we partitionthis set into O(i) equivalence classes. These classesare intimately related to the branching structure ofthe first i paths, which we call the path branchingstructure Ti . This is a rooted tree that compactlyencodes how the first i paths branch off from eachother topologically, and it can be defined procedurallyas follows. (N.B. The procedural definition is not partof our algorithm; it is just a convenient way to describethe path branching structure.)The subroutine to construct Ti is called withparameters (s, Πi ), where s is the fixed source andΠi {P1 , P2 , . . . , Pi } is the set of the first i shortestpaths. We initialize Ti to the singleton root node s.Let (s, a, b, . . . , u) be the longest subpath that is acommon prefix of all the paths in Πi . We expand Tiby adding a node labeled u, and creating the branch(s, u). The node u is the child of s. The set of paths{P1 , P2 , . . . , Pi } is defined to be the path bundle of(s, u) and denoted by B(s, u).1 We now partition thepath bundle B(s, u) into sets S1 , S2 , . . . , Sα such that1 Strictly speaking, the bundle notation should have thesubscript i to indicate that it refers to a branch in tree Ti . Wedrop this subscript to keep the notation simple, since the choiceof branching structure will always be clear from the context.
sabc{1,2,3,4}P2P4P3efin Ti for each of the k shortest paths, which is whywe distinguish the t nodes by their prefix paths (e.g.,tP ). Likewise, a pair of vertices u, v may correspondto multiple branches, each with its own branch path.The following lemma is 4t P1t P2t(i)(ii)Figure 2: (i) Four shortest paths, P1 , . . . , P4 . (ii) Theassociated path branching structure.all paths in Sj follow the same edge after u, and pathsin different groups, Sj , Sl , follow distinct edges. Wethen make recursive calls (u, Sj ), for j 1, 2, . . . , α,to complete the construction of Ti . The recursionstops when Sj 1, i.e., Sj contains a single pathP . In this case we create a leaf node labeled tP ,representing the target vertex parameterized by thepath that reaches it, and associate the bundle {P } withthe branch (u, tP ). See Figure 2 for an example of apath branching structure.Remark: It is possible that the paths in the bundleB(s, u) have no overlap, meaning u s. In this case,the branch (s, u) is not created, and we go directly tothe recursive calls.For any given branch (u, v), B(u, v) is exactly theset of paths that terminate at leaf descendants of v.The bundles are not maintained explicitly; rather, theyare encoded in the path branching structure. Eachbranch (u, v) has a path in G associated with it. Thispath, denoted branchPath(u, v), is shared by all thepaths in B(u, v). Its endpoints are the vertices of Gcorresponding to nodes u and v. The first edge ofbranchPath(u, v) is the lead edge of the path, denotedlead (u, v). A node u in Ti has a prefix path associatedwith it, denoted prefixPath(u). The prefix path is theconcatenation of the branch paths for all the branchesfrom s to u in Ti . Thus a shortest path P is equal toprefixPath(tP ).It is important to note the distinction betweennodes in Ti and their corresponding vertices in G. Asingle vertex u V may have up to k correspondingnodes in Ti , depending on how many different pathsfrom s reach it. For example, vertex t has one nodeLemma 2.1. The path branching structure Ti has O(i)nodes and exactly i leaves.The preceding lemma would apply to a branchingstructure built from any i simple paths from s to t—it does not depend on the paths of Πi being shortestpaths. The following lemma characterizes the branchesof Ti more precisely, and it does depend on the shortness of the paths.Lemma 2.2. Let (u, v) be a branch in Ti . Let Pbe the shortest path from vertex u to vertex t in Gthat starts with lead (u, v) and is vertex-disjoint fromprefixPath(u). Then branchPath(u, v) P .Proof. Recall that the ith path Pi is the shortest paththat is not an element of Πi 1 . Therefore, Pi mustbranch off from each path in Πi 1 . Let x be the vertexof Pi farthest from s where Pi branches off from a pathin Πi 1 . Since Ti 1 contains exactly the paths in Πi 1 ,Pi branches off from some branchPath(·, ·) of Ti 1 at x.Let e be the edge on Pi that follows x. Because Pi isthe shortest simple path not in Πi 1 , it must a fortioribe the shortest simple path that branches off from Ti 1at x and follows e. The simplicity requirement meansthat the part of Pi after x must be disjoint from allthe vertices on the prefix path in Ti 1 from s to x.However, the only other requirement on the part of Piafter e is that it be as short as possible; this implies thatthe part of the path after x contains no loops. Moregenerally, for every edge e0 on Pi after x, the subpathoptimality property of shortest paths implies that thepart of Pi after e0 is the shortest path from the headvertex of e0 to t that avoids the vertices of the prefixof Pi up through the tail vertex of e0 .Any branch (u, v) in Ti is a subset of a branch(x, tPj ) that was created as a branch off Tj 1 for somej i. (Branches are not moved by later branches,only subdivided.) The edge lead (u, v) belongs tobranchPath(x, tPj ), and hence as noted in the preceding paragraph, the part of Pj after u, which containsbranchPath(u, v), is the shortest path that starts withlead (u, v) and is vertex-disjoint from prefixPath(u).We associate the equivalence classes of candidatepaths with the nodes and branches of Ti , as follows.Consider a non-leaf node u Ti , and suppose that the
children of u are labeled v1 , v2 , . . . , vα . We associateone equivalence class with each branch out of u,denoted C(u, vj ), and one with node u itself, denotedC(u). The class C(u, vj ) consists of those paths ofRi that overlap with the paths in prefixPath(vj ) upto and including the lead edge lead(u, vj ), but thisoverlap does not extend to vj . That is, each pathof C(u, vj ) diverges from prefixPath(vj ) somewherestrictly between u and vj . The final set C(u) consistsof those paths that overlap with each prefixPath(vj ) upto u, but no farther. That is, these paths branch off atu, using an edge that is distinct from any of the leadedges lead(u, vj ), for j 1, 2, . . . , α. The equivalencepartition associated with the path branching structureTi is the collection of these sets over all branches andnon-leaf nodes of Ti .For instance, consider node a in Figure 2. Thereare three equivalence classes associated with a: classC(a, c) includes those paths that share the subpathfrom s to a with P3 , P4 , and branch off somewherestrictly between a and c (assume that the subpath froma to c contains more than one edge). Similarly, theclass C(a, b) contains paths that coincide with P1 , P2until a, then branch off before b. Finally, the class C(a)contains paths that coincide with P1 , . . . , P4 up to a,then branch off at a.Lemma 2.3. Every path from s to t that is not amongthe i shortest paths belongs to one of the equivalenceclasses associated with the nodes and branches of Ti .The number of equivalence classes associated with thepath branching structure Ti is O(i).Proof. Consider a path P different from the first ishortest paths. Suppose Pj , where 1 j i, is thepath that shares the longest common prefix subpathwith P . In Ti , let (u, v) be the first branch where Pand Pj diverge. Then P belongs in the equivalenceclass associated with either u or (u, v). Finally, thetotal number of equivalence classes is O(i) becauseeach node and branch of Ti has only one equivalenceclass associated with it, and there are O(i) nodes andbranches in Ti .We are now ready to describe our algorithm forenumerating the k shortest simple paths.3Computing the k ShortestPathsWe maintain a heap, which records the minimumpath length from each of the O(i) equivalence classes.Clearly, the next shortest path from s to t is thesmallest of these O(i) heap entries. Once this path ischosen (and deleted from the heap), the path branchingstructure is modified, and so is the equivalence classpartition. Computationally, this involves refining oneequivalence class into at most four classes. For eachclass, we determine the minimum element, and theninsert it into the heap. See Figure 3.Algorithm k-ShortestPaths Initialize the path branching structure T to contain a single node s, and put path(s, t) in the heap.There is one equivalence class C(s) initially, whichcorresponds to all the s–t paths. Repeat the following steps k times.1. Extract the minimum key from the heap.The key corresponds to some path P .2. If P belongs to an equivalence class C(u) forsome node u then(a) Add a new branch (u, tP ) to T thatrepresents the suffix of P after u.(b) Remove from C(u) the paths that shareat least one edge with P after u andput all of them except P into the newlycreated equivalence class C(u, tP ).3. Else (P belongs to the equivalence classC(u, v) for some branch (u, v))(a) Let w be the vertex where P branches offfrom branchPath(u, v).(b) Insert a new node labeled w, and splitthe branch (u, v) into two new branches(u, w) and (w, v). Add a second branch(w, tP ) that represents the suffix of Pafter w.(c) Redistribute the paths of C(u, v) \ Pamong the four new equivalence classesC(u, w), C(w, v), C(w, tP ), and C(w),depending on where they branch frombranchPath(u, v) and/or P .i. Paths branching off branchPath(u, v)before node w belong to C(u, w).ii. Paths branching off branchPath(w, v)after node w belong to C(w, v).iii. Paths branching off P after node wbelong to C(w, tP ).iv. Paths branching off both P andbranchPath(u, v) at node w belong toC(w).
4. For each new or changed equivalence class (atmost four), compute the shortest path froms to t that belongs to the class. Insert thesepaths into the heap.ssuvtxttuwxtvttttt(i)(ii)Figure 3: Illustration of how the equivalence classpartition and branching structure change with theaddition of a new path. The left figure shows thestructure before adding the new path. There is anequivalence class for each non-leaf node and branchof the tree. The right figure shows the portion of thestructure that is affected if the newly added path camefrom the class belonging to branch (u, v). The classescorresponding to the node and three branches that areinside the shaded oval are modified.Lemma 3.1. Algorithm k-ShortestPaths correctlycomputes the ith shortest path, the branching structureTi , and the equivalence class partition of the candidatepaths Ri , for each i from 1 to k.The complexity of the algorithm described aboveis dominated by Step 4. Step 1 takes only O(log k)time per iteration of the repeat loop, and Steps 2and 3 take O(n) time for path manipulation. Theredistribution of candidate paths among equivalenceclasses is conceptual—the hard work is computing theminimum element in each class in Step 4. In thefollowing section, we discuss how to implement thisstep efficiently.Remark: Our algorithm is conceptually similar tothose of Yen and Lawler. The main difference isthat our algorithm partitions the candidate paths intoequivalence classes determined by the path branchingstructure, and those algorithms do not. This additionalstructure together with the fast replacement pathssubroutine (Section 4) is the key to our algorithm’sefficiency.4The Replacement PathsProblemThe key step in our k shortest paths algorithm isthe computation of the best path in each equivalenceclass, which can be formulated as a replacement pathsproblem. Let H (V, E) be a directed graph withnon-negative edge weights, and let x, y be two specifiednodes. Let P {v1 , v2 , . . . , vm }, where v1 x,and vm y, be the shortest path from x to y inH. We want to compute the shortest path from x toy that does not include the edge (vi , vi 1 ), for eachi {1, 2, . . . , m 1}. We call this the best replacementpath for (vi , vi 1 ); the reference to the source x andtarget y is implicit.A naı̈ve algorithm would require m 1 invocationsof the single-source shortest path computation: run theshortest path algorithm in graph H i , where H i is thegraph H with edge (vi , vi 1 ) deleted. The followingalgorithm does batch computation to determine allthe replacement paths in O( E V log V ) time; asmentioned earlier, it can fail for some directed graphs,but the failure can easily be detected. This algorithm isa slight simplification of the one in [7]. For full detailsof the algorithm’s data structures, refer to that paper.Algorithm Replacement1. In the graph H, let X be a shortest path tree fromthe source x to all the remaining nodes, and let Ybe a shortest path tre
Finding the k Shortest Simple Paths: . Our algorithm is based on a replacement paths algorithm proposed recently by Hershberger and Suri [7], and can yield a factor Θ(n) improvement for this problem. But there is a caveat: the fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được
shortest one. Yen (1971) first introduced a k-shortest path searching method by deleting node from the network, and then several k-shortest algorithms have been suggested. There are two groups of k-shortest path algorithm. The difference is one allow loops in result paths and another don’t. In transportation network the latter is always used .
The classical K -Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for v ehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely
