DOC PREVIEW
UT Dallas CS 6363 - notes-6363-001-2015s-25-p3

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

c� Balaji Raghavachari 186 Algorithm Design and Analysis✬✫✩✪Correctness of Dijkstra’s algorithm• Using induction on the number of calls to the Relaxprocedure, u.d is an upper bound on δ(s, u) (theshortest path distance from s to u).• Loop invariant: at the start of each iteration of thewhile loop, u.d = δ(s, u) for all vertices u ∈ S. Also, forvertices in v ∈ V − S, v.d is the length of a shortest pathfrom s to v whose internal vertices are only from S.• Consider vertex u with minimum u.d returned byExtract-Min. We show that u.d = δ(s, u). Considershortest path P from s to u.• If all internal nodes of P are from S, then u.d = δ(s, u)(see loop invariant).c� Balaji Raghavachari 187 Algorithm Design and Analysis✬✫✩✪• Otherwise, let y be the first vertex on the path from sthat is outside S. By loop invariant, y.d = δ(s, y).• Since all edge-weights are nonnegative, δ(s, y) ≤ δ(s, u).Therefore, y.d = δ(s, y) ≤ δ(s, u) ≤ u.d.• But u.d is minimum in V − S, and therefore u.d ≤ y.d.• Therefore u.d = y.d and hence δ(s, u) = u.d.• To show that t he loop invariant holds after vertex u isadded to S: consider v ∈ V − S. If shortest path from sto v whose internal nodes are only from S goes throughu, then the call to Relax(u,v) updates v.d to beu.d + w(u, v).c� Balaji Raghavachari 191 Algorithm Design and Analysis✬✫✩✪Shortest paths by extension• Consider the following recursive characterization ofshortest paths: let dk(u, v) be the length of a shortestpath from vertex u to vertex v that contains at most kedges. The base case is d1(u, v) = w(u, v). For longerpaths, the recurrence is:dk+1(u, v) = minp∈V{dk(u, p) + w(p, v)}• We need to calculate d|V |−1(u, v), since any (simple)shortest path contains at most |V | − 1 edges.• Above recursive scheme ca n be implement ed as adynamic program that runs in O(|V |4) t ime.c� Balaji Raghavachari 192 Algorithm Design and Analysis✬✫✩✪Speeding up the algorithm• To compute Anfor a given matrix A, instead of nmatrix multiplications, we can solve the problem usingO(log n) ma trix multiplications by repeated squaring.• Why extend paths only one edge at a time? Why notsplit the shortest path into two (roughly) equal parts?New formulation:d2k(u, v) = minm∈V{dk(u, m) + dk(m, v)}• With this formulation, k doubles in each step.Therefore, in O(log |V |) iterations, we get the answer.• Dynamic program implements this recurrence inO(|V |3log |V |) time. Temporary matrix T is used tostore D2kto reduce space used.c� Balaji Raghavachari 193 Algorithm Design and Analysis✬✫✩✪APSP by extension: dynamic programAP SP (G)for u ∈ V dofor v ∈ V doD[u, v] ← w(u, v)k ← 1while k < |V | − 1 dofor u ∈ V dofor v ∈ V doT [u, v] ← D[u, v] // Temporary matrixfor m ∈ V doif T [u, v] > D[u, m] + D[m, v] thenT [u, v] ← D[u, m] + D[m, v]D ← T // Copy D2kfrom T back to Dk ← 2 ∗ kreturn Dc� Balaji Raghavachari 194 Algorithm Design and Analysis✬✫✩✪Sample run of APSP by extension132457 16742−53−4D1D2D40 3 7 ∞ -4∞ 0 ∞ 1 7∞ 4 0 ∞ ∞2 ∞ -5 0 ∞∞ ∞ ∞ 6 00 3 7 2 -43 0 -4 1 7∞ 4 0 5 112 -1 -5 0 -28 ∞ 1 6 00 1 -3 2 -43 0 -4 1 -17 4 0 5 32 -1 -5 0 -28 5 1 6 0c� Balaji Raghavachari 195 Algorithm Design and Analysis✬✫✩✪Floyd-Warshall algorithm• Dynamic program based on a new recurrence. Verticesare numbered 1, 2, ..., |V |. Define d(k)(u, v) to be thelength of a shortest path from u to v in which onlynodes 1, 2, ..., k may be used as internal nodes. Clearly,d(0)(u, v) = w(u, v). For k > 0,d(k)(u, v) = min{d(k−1)(u, v), d(k−1)(u, k) + d(k−1)(k, v)}Dynamic program for computing d(n)(ij) runs in O(|V |3):for u ∈ V dofor v ∈ V doD[u, v] ← w(u, v)for k ← 1to|V | dofor u ∈ V dofor v ∈ V doD[u, v] ← min(D[u, v], D[u, k] + D[k, v])c� Balaji Raghavachari 196 Algorithm Design and Analysis✬✫✩✪Sample run of Floyd-Warshall’s algorithm for APSP132457 16742−53−4D(0)D(1)D(2)0 3 7 ∞ -4∞ 0 ∞ 1 7∞ 4 0 ∞ ∞2 ∞ -5 0 ∞∞ ∞ ∞ 6 00 3 7 ∞ -4∞ 0 ∞ 1 7∞ 4 0 ∞ ∞2 5 -5 0 -2∞ ∞ ∞ 6 00 3 7 4 -4∞ 0 ∞ 1 7∞ 4 0 5 112 5 -5 0 -2∞ ∞ ∞ 6 0D(3)D(4)D(5)0 3 7 4 -4∞ 0 ∞ 1 7∞ 4 0 5 112 -1 -5 0 -2∞ ∞ ∞ 6 00 3 -1 4 -43 0 -4 1 -17 4 0 5 32 -1 -5 0 -28 5 1 6 00 1 -3 2 -43 0 -4 1 -17 4 0 5 32 -1 -5 0 -28 5 1 6


View Full Document

UT Dallas CS 6363 - notes-6363-001-2015s-25-p3

Documents in this Course
Exam #1

Exam #1

5 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

greedy

greedy

4 pages

siphon

siphon

18 pages

hwk5

hwk5

3 pages

Load more
Download notes-6363-001-2015s-25-p3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view notes-6363-001-2015s-25-p3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view notes-6363-001-2015s-25-p3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?