[PDF] Shortest Paths PDF sp.pdf

otherwise • A shortest path from vertex u to vertex v is then defined as any path p with weight w(p) = δ(u, v) Page 2 Example s a b c f t 3 4 6 2 5 7 1 8 4 Correctness of Dijkstra's algorithm Dijkstra's algorithm, run on a weighted, directed

AQA Computer Science A-Level 4 3 6 Optimisation algorithms Extra Resources www pmt education Page 2 Dijkstra's Algorithm - an example

[PDF] Dijkstras algorithm - csail

How Long Is Your Path? • Directed graph • Edge‐weight function • Path • Weight of , denoted , is v 1 v 2 v 3 v 4 v 5 4 −2 −5 1 Example:

[PDF] Shortest Paths - Algorithms

shortest-paths properties ‣ Dijkstra's algorithm ‣ edge-weighted DAGs ‣ negative weights Given an edge-weighted digraph, find the shortest path from s to t

[PDF] PATH FINDING - Dijkstras Algorithm - Computer Science - Indiana

13 déc 2014 · For example the edge cost between A and C is 1 Using the above graph the Dijkstra algorithm is used to determine the shortest path from the

Shortest Paths

Input: weighted, directed graphG= (V;E), with weight functionw: E!R. Thew eightof path p=< v0;v1;:::;vk>is the sum of the weights of its constituent edges: w(p) =k X i=1w(vi1;vi):

Theshortest-path w eightfrom utovis

(u;v) =fminfw(p)gif there is a pathpfromutov ;

1otherwise:

Ashortest path from v ertexuto vertexvis then dened as any path pwith weightw(p) =(u;v).

Examplesa

bc ft 3 4 62
5 7 18 4

Solutionsa

bc ft 3 4 62
5 7 18 4 3 5 6 410

Shortest Paths

Shortest Path Variants

Single Source-Single Sink

Single Source (all destinations from a sources)

All Pairs

Defs:

Let(v)be the real shortest path distance fromstov

Letd(v)be a value computed by an algorithm

Edge Weights

All non-negative

Arbitrary

Note:

Must ha veno negativ ecost cycles

Single Source Shortest Paths

Key Property: Subpaths of shortest paths are shortest paths

Giv ena

weighted, directed graphG= (V;E)with weight functionw:E!R, let p=< v1;v2;:::;vk>be a shortest path from vertexv1to vertexvkand, for anyiandjsuch that1ijk, letpij=< vi;vi+1;:::;vj>be the subpath ofpfrom vertexvito vertexvj. Then,pijis a shortest path fromvitovj.

Note: this is optimal substructure

Corollary 1

F orall edges (u;v)2E,

(v)(u) +w(u;v)

Corollary 2

Shortest paths follo wa tree of edges for whic h

(v) =(u) +w(u;v) More precisely, any edge in a shortest path must satisfy (v) =(u) +w(u;v)

Relaxation

Relax(u;v;w)

1 ifd[v]> d[u] +w(u;v)

2 thend[v] d[u] +w(u;v)

3[v] u(keep track of actual path)

Lemma:

Assume that w einitialize all d(v)to1,d(s) = 0and execute a series of Relax operations. Then for allv,d(v)(v).

Lemma:

Let P=e1;:::;ekbe a shortest path fromstov. After initial- ization, suppose that we relax the edges ofPin order (but not necessarily consecutively). Thend(v) =(v).

Examplesa

b c d 26
-83 5 5 6 4 e -1

Algorithms

Goal of an algorithm:

Relax the edges in a shortest path in order (but

not necessarily consecutively).

Algorithms

Goal of an algorithm:

Relax the edges in a shortest path in order (but

not necessarily consecutively).

Bellman-Ford(G;w;s)

1Initialize-Single-Source(G;s)

2 fori 1tojV[G]j 1

3 do for each edge(u;v)2E[G]

4 doRelax(u;v;w)

5 for each edge(u;v)2E[G]

6 do ifd[v]> d[u] +w(u;v)

7 then returnfalse

8 returntrue

InitializeSingleSource(G;s)

1 for each vertexv2V[G]

2 dod[v] 1

3[v] nil

4d[s] 0

Examplesa

b c d 26
-83 5 5 6 4 e -1

Correctness of Bellman Ford

Every shortest path must be relaxed in order

If there are negative weight cycles, the algorithm will return false

Running TimeO(V E)

All edges non-negative

Dijkstra's algorithm, a greedy algorithm

Similar in spirit to Prim's algorithm

Idea: Run a discrete event simulation of breadth-rst-search. Figure out how to implement it eciently

Can relax edges out of each vertex exactly once.

Dijkstra(G;w;s)

1Initialize-Single-Source(G;s)

2S ;

3Q V[G]

4 whileQ6=;

5 dou Extract-Min(Q)

6S S[ fug

7 for each vertexv2Adj[u]

8 doRelax(u;v;w)

Examplesa

bc ft 3 4 62
5 7 18 4

Running Time and Correctness

Correctness of Dijkstra's algorithm

Dijkstra's algorithm, run on a w eighted,

directed graphG= (V;E)with nonnegative weight functionwand source s, terminates withd[u] =(s;u)for all verticesu2V.

Edecrease keys andVdelete-min's

O(ElogV)using a heap

O(E+VlogV)using a Fibonacci heap

We will see algorithm using a Relaxed Heap

Shortest Path in a DAG

Dag-Shortest-Paths(G;w;s)

1 topologically sort the vertices ofG

2Initialize-Single-Source0(G;s)

3 for eachutaken in topological order

4 do for eachv2Adj[u]

5 doRelax(u;v;w)

Examplesa

bc ft 3 4 62
5 7 18 4

Correctness and Running Time

Correctness

If a w eighted,directed graph G= (V;E)has source vertexsand no cycles, then at the termination of theDag-Shortest-Pathsprocedure, d[v] =(s;v)for all verticesv2V, and the predecessor subgraphGis a shortest-paths tree.

[PDF] [PDF] Shortest Paths