词条 | Edge disjoint shortest pair algorithm |
释义 |
Edge disjoint shortest pair algorithm is an algorithm in computer network routing.[1] The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices as follows:
Suurballe's algorithm solves the same problem more quickly by reweighting the edges of the graph to avoid negative costs, allowing Dijkstra's algorithm to be used for both shortest path steps. AlgorithmG = (V, E) d(i) – the distance of vertex i (i∈V) from source vertex A; it's the sum of arcs in a possible path from vertex A to vertex i. Note that d(A)=0; P(i) – the predecessor of vertex I on the same path. Z – the destination vertex Step 1. Start with d(A)=0, d(i) = l (Ai), if i∈ΓA; Γi ≡ set of neighbor vertices of vertex i,l(ij) = length of arc from vertex i to vertex j. = ∞, otherwise (∞ is a large number defined below); Assign S = V- Step 2. a) Find j∈S such that d(j) = min d(i), i∈S. b) Set S = S – {j}. c) If j = Z (the destination vertex), END; otherwise go to Step 3. Step 3. ∀i∈Γj, if d(j)+l(ij) |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。