shortest path algorithm ppt

shortest path routing algorithm in computer networks ppt and all pair shortest path algorithm with example ppt
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
7. NETWORK FLOW III assignment problem ‣ input-queued switching ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 6:40 AM7. NETWORK FLOW III assignment problem ‣ input-queued switching ‣ SECTION 7.13Assignment problem Input. Weighted, complete bipartite graph G = (X ∪ Y, E) with X = Y . Goal. Find a perfect matching of min weight. 15 0' 0 7 3 5 1 1' 6 2 9 4 2 1 2' X Y 3Assignment problem Input. Weighted, complete bipartite graph G = (X ∪ Y, E) with X = Y . Goal. Find a perfect matching of min weight. 15 0' 0 7 3 min-cost perfect matching 5 M = 0-2', 1-0', 2-1' 1 1' 6 cost(M) = 3 + 5 + 4 = 12 2 9 4 2 1 2' X Y 4Princeton writing seminars Goal. Given m seminars and n = 12m students who rank their top 8 choices, assign each student to one seminar so that: Each seminar is assigned exactly 12 students. Students tend to be "happy" with their assigned seminar. Solution. Create one node for each student i and 12 nodes for each seminar j. Solve assignment problem where c is some function of the ranks: ij f(rank(i,j))B7 i`MFb j c = ij B7 i/Q2bMQi`MF j 5Locating objects in space Goal. Given n objects in 3d space, locate them with 2 sensors. Solution. Each sensor computes line from it to each particle. Let c = distance between line i from censor 1 and line j from sensor 2. ij Due to measurement errors, we might have c 0. ij Solve assignment problem to locate n objects. 6Kidney exchange If a donor and recipient have a different blood type, they can exchange their kidneys with another donor and recipient pair in a similar situation. Can also be done among multiple pairs (or starting with an altruistic donor). 7Kidney exchange 1 3 2 8 3 1 3 2 8 3 6 2 5 9 4 6 2 5 9 4 4 7 5 1 6 4 7 5 1 6 weight = 3 + 5 + 7 + 8 + 4 = 27 weight = 2 + 5 + 8 + 6 + 1 + 9 = 31 8Applications Natural applications. Match jobs to machines. Match personnel to tasks. Match PU students to writing seminars. Non-obvious applications. Vehicle routing. Kidney exchange. Signal processing. Multiple object tracking. Virtual output queueing. Handwriting recognition. Locating objects in space. Approximate string matching. Enhance accuracy of solving linear systems of equations. 9Bipartite matching Bipartite matching. Can solve via reduction to maximum flow. Flow. During Ford-Fulkerson, all residual capacities and flows are 0-1; flow corresponds to edges in a matching M. 1 Residual graph G simplifies to: M 1 1 If (x, y) ∉ M, then (x, y) is in G . M t s If (x, y) ∈ M, then (y, x) is in G . M X Y Augmenting path simplifies to: Edge from s to an unmatched node x ∈ X, Alternating sequence of unmatched and matched edges, Edge from unmatched node y ∈ Y to t. 10Alternating path Def. An alternating path P with respect to a matching M is an alternating sequence of unmatched and matched edges, starting from an unmatched node x ∈ X and going to an unmatched node y ∈ Y. Key property. Can use P to increase by one the cardinality of the matching. Pf. Set M ' = M ⊕ P. symmetric difference y y y x x x matching M alternating path P matching M' 11Assignment problem: successive shortest path algorithm Cost of alternating path. Pay c(x, y) to match x-y; receive c(x, y) to unmatch. 1 10 1' 6 P = 2 → 2' → 1 → 1' cost(P) = 2 - 6 + 10 = 6 7 2 2 2' Shortest alternating path. Alternating path from any unmatched node x ∈ X to any unmatched node y ∈ Y with smallest cost. Successive shortest path algorithm. Start with empty matching. Repeatedly augment along a shortest alternating path. 12Finding the shortest alternating path Shortest alternating path. Corresponds to minimum cost s↝t path in G . M 10 1 1' 0 -6 s t 7 0 2 2 2' Concern. Edge costs can be negative. Fact. If always choose shortest alternating path, then G contains no M negative cycles ⇒ can compute using Bellman-Ford. Our plan. Use duality to avoid negative edge costs (and negative cycles) ⇒ can compute using Dijkstra. 13Equivalent assignment problem Duality intuition. Adding a constant p(x) to the cost of every edge incident to node x ∈ X does not change the min-cost perfect matching(s). Pf. Every perfect matching uses exactly one edge incident to node x. ▪ original costs c(x, y) modified costs c'(x, y) 15 0' 18 0' 0 0 p(0) = 3 7 10 3 6 add 3 to all edges incident to node 0 5 5 6 1' 1 6 1' 1 2 2 9 9 4 4 2 1 2' 2 1 2' X Y X Y 14Equivalent assignment problem Duality intuition. Subtracting a constant p(y) to the cost of every edge incident to node y ∈ Y does not change the min-cost perfect matching(s). Pf. Every perfect matching uses exactly one edge incident to node y. ▪ original costs c(x, y) modified costs c'(x, y) 15 0' 10 0' 0 p(0') = 5 0 7 7 3 3 subtract 5 from all edges incident to node 0' 5 0 6 1' 1 6 1' 1 2 2 9 4 4 4 2 1 2' 2 1 2' X Y X Y 15Reduced costs p Reduced costs. For x ∈ X, y ∈ Y, define c (x, y) = p(x) + c(x, y) – p(y). Observation 1. Finding a min-cost perfect matching with reduced costs is equivalent to finding a min-cost perfect matching with original costs. p original costs c(x, y) reduced costs c (x, y) 15 0' 4 0' 0 p(0') = 11 0 p(0) = 0 7 1 3 0 5 0 6 1' p(1') = 6 1 6 1' p(1) = 6 1 2 5 p 9 0 c (1, 2') = p(1) + 2 – p(2') 4 0 2 1 2' 2 0 2' p(2') = 3 p(2) = 2 X Y X Y 16Compatible prices Compatible prices. For each node v ∈ X ∪ Y, maintain prices p(v) such that: p c (x, y) ≥ 0 for all (x, y) ∉ M. p c (x, y) = 0 for all (x, y) ∈ M. Observation 2. If prices p are compatible with a perfect matching M, then M is a min-cost perfect matching. p reduced costs c (x, y) Pf. Matching M has 0 cost. ▪ 4 0' 0 1 0 0 1 6 1' 5 0 0 2 0 2' X Y 17Successive shortest path algorithm SUCCESSIVE-SHORTEST-PATH (X, Y, c) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ prices p are M ← ∅. compatible with M p FOREACH v ∈ X ∪ Y : p(v) ← 0. c (x, y) = c(x, y) ≥ 0 WHILE (M is not a perfect matching) p d ← shortest path distances using costs c . p P ← shortest alternating path using costs c . M ← updated matching after augmenting along P. FOREACH v ∈ X ∪ Y : p(v) ← p(v) + d(v). RETURN M. _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 18Successive shortest path algorithm Initialization. M = ∅. For each v ∈ X ∪ Y : p(v) ← 0. original costs c(x, y) p(0) = 0 p(0') = 0 15 0 0' 7 3 p(1) = 0 p(1') = 0 5 s t 1 6 1' 2 9 4 2 1 2' p(2) = 0 p(2') = 0 19Successive shortest path algorithm Initialization. M = ∅. For each v ∈ X ∪ Y : p(v) ← 0. p reduced costs c (x, y) p(0) = 0 p(0') = 0 15 0 0' 7 3 p(1) = 0 p(1') = 0 5 s t 1 6 1' 2 9 4 2 1 2' p(2) = 0 p(2') = 0 20