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:

  • Run the shortest path algorithm for the given pair of vertices
  • Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex
  • Make the length of each of the above arcs negative
  • Run the shortest path algorithm (Note: the algorithm should accept negative costs)
  • Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.

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.

Algorithm

G = (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-{A}, where V is the set of vertices in the given graph.
Assign P(i) = A, ∀i∈S.

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) < d(i),
a) set d(i) = d(j) + l(ij), P(i) = j.
b) S = S ∪{i}
Go to Step 2.
gollark: I tick those boxes there to allow it to index those sites.
gollark: I've made a bit of a frontend for my search engine thing. Though it can't actually do search yet, only crawl/index/whatever pages.
gollark: Basically, if I want to run a search it just goes `SELECT * FROM page_tokens WHERE token = 'one token in search query'` or something like that, and it now has a list of pages with the right token, and SQLite can execute this query relatively fast.
gollark: I mean, as far as I can tell there isn't really a faster *and* more storage-efficient way to do search than the inverted-index page_tokens thing.
gollark: ```sqlCREATE TABLE crawl_queue ( id INTEGER PRIMARY KEY, url TEXT NOT NULL UNIQUE, lockTime INTEGER, added INTEGER NOT NULL, referrer TEXT);CREATE TABLE pages ( id INTEGER PRIMARY KEY, url TEXT NOT NULL UNIQUE, rawContent BLOB NOT NULL, rawFormat TEXT NOT NULL, textContent TEXT NOT NULL, updated INTEGER NOT NULL);CREATE TABLE page_tokens ( id INTEGER PRIMARY KEY, page INTEGER NOT NULL REFERENCES pages(id), token TEXT NOT NULL, weight REAL NOT NULL);CREATE TABLE links ( id INTEGER PRIMARY KEY, toURL TEXT NOT NULL, fromURL TEXT NOT NULL, lastSeen INTEGER NOT NULL, UNIQUE (toURL, fromURL))```Here is the database.

References
  1. Bhandari, Ramesh (1999). Survivable networks: algorithms for diverse routing. 477. Springer. p. 46. ISBN 0-7923-8381-8.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.