Shortest paths algorithms Flashcards

Question 1

Q

What is the generic algorithm for finding delta(s,v) for all v’s?

Answer

A

Init:

d(s)=0, d(v)=infinity

loop:

while (exists an edge (u,v) for which d(v)>d(u)+w(u,v):
- find such an edge and call Relax(u,v,w)

end:

return d(v) for every v

Question 2

Q

Lower bound claim

All along the run of the algorithm, for all v, the inequality: d(v)>=delta(s,v) is satisfied, and if d(v)

proof that claim.

Answer

A

Using induction on the number of Relax operations

base: after initilization
- v is not s, delta(s,v)
- d(s)=0 = delta(s,s)
Induction assumption
- by the end of the i-1 step, the assumption is satisfied.
step
- Let’s look at Relax on the ith step.
- case 1: no update
  - array d stays the same
- case 2: updated
  - d(v)-the only one that has changed.
  - d(v)=d(u)+w(u,v)
  - d(u)>=delta(s,u) (by I.A)
  - delta(s,u)+w(u,v) >= delta(s,v)
    - observation.
  - d(v)>= delta(s,u)+w(u,v)>=delta(s,v)
  - since d(v) is updated:
    - d(v)
  - d(u) - a weight of some Psu.
  - d(v)=d(u)+w(u,v)*-**weight of Psu+(u,v)*

Question 3

Q

What is the correctness statement for the generic algorithm?

Answer

A

If through the run of the algorithm, for every edge (u,v), d(v)<=d(u)+w(u,v) is satisfied(that is, the algorith, stops), then, for every v, d(v)=delta(s,v).

Question 4

Q

What is the correctness statement proof for the generic algorithm, in case it stops?

Answer

A

Assume the algorithm stopped
- for all (u,v) in E, d(v)<=d(u)+w(u,v)
Assume in negation: there exists x in V s.t:
- d(x) != delta(s,x)
Let Psx the lightest path from s to x.
let v be the first vertex in P s.t. d(v) != delta(s,v)
- by the lower bound claim: d(v)>delta(s,v)
let u be the preceding vertex to v in P
- d(u) = delta(s,u)
By sub-paths of a shortests path prinicipal
- delta(s,u)+w(u,v)=delta(s,v).
d(v)<=d(u)+w(u,v)=delta(s,u)+w(u,v)=delta(s,v)
- contradiction

Question 5

Q

What is the “full” correctness statement of the generic algorithm?

Question 6

Q

What is the exact definition of

rooted tree in vertex s

Answer

A

Directed graph is called rooted tree in vertex s if every vertex in the graph is accessible from s, and it is accessible only via one path

Question 7

Q

Which data structure can help us maintain a rooted tree in vertex s?

Answer

A

It can be maintaind via array of length |V|

The index of a cell represents some vertex*
The content of cell v is former(v)*

Question 8

Q

“lightest paths tree T for graph G and source s”

what is it?

Answer

A

It is a rooted tree in vertex s which satisfies:

for every v, the only path from s to v in T is the lightest path from s to v in G.

Question 9

Q

General algorithm, what claims are used in order to prove the correctness statement?

Question 10

Q

Generic algorithm, how the first claim is proved?

Answer

A

N.T.F - d(u) = delta(s,u)
lower bound claim - d(u)>=delta(s,u)
d(v)=d(u)+w(u,v) = delta(s,v)
- last Relax operation -> d(v)=delta(s,u)
delta(s,v)<= delta(s,u)+w(u,v)
d(u)+w(u,v) = delta(s,v)<=delta(s,u)+w(u,v)
- d(u)<=delta(s,u)
d(u)>=delta(s,u) & d(u)<=delta(s,u)
- d(u) = delta(s,u)

Question 11

Q

General algorithm, proof for the 2nd claim.

What is the induction based on

Answer

A

It is based on the size of V’. That is, |V’|.

Question 12

Q

Genereal algorithm, proof of the 2nd claim.

What is the base case for the induction proof?

Answer

A

|V’| = 1.*

That is:

V’ = {s}
E’ = empty set.

Trivial.

Question 13

Q

Generic algorithm, proof of the 2nd claim.*
what is the step in the induction?*

Answer

A

we look at the next vertex v to be added into V’. That is, the next vertex for which d(v) = delta(s,v).*
N.T.S: T=(V’ U {v}, E’ U {former(v),v})* is a shortest paths tree.

Question 14

Q

Generic algorithm, proof of the 2nd claim.

What is the proof for the step phase of the induction?

Answer

A

According to the 1st claim: d(v)=delta(s,v) means:

former(v) = delta(s,former(v))
therefore, former(v) is in V’ too.

Proof: T is a tree.

(V’,E’) is a tree.
former(v) is in V’
we added an edge from former(v) to a new vertex v in V’.

proof: T is a shortest paths tree from s

I.A holds for all other vertices. N.T.F for v.
The path Psv in T is composed of:
- Psformer(v) + (former(v),v)
by the assumption: d(v)=delta(s,v)
by claim 1: d(former(v)) = delta(s,former(v))
w(Psv)=w(Psformer(v))+w(former(v),v) =
delta(s,former(v))+w(fomer(v),v)=d(v) = delta(s,v)

Question 15

Q

Generic algorithm, what is the proof for the correctness statement, using the claims.

Answer

A

If the algorithm stops, then we proved that for all v, d(v) = delta(s,v) is satisfied.*
Therefore, the Tree V’=V E’={(former(v),v): v!=s} can be created, and by the 2nd claim - G = (V’,E’) is a lightests paths tree from s in G.*.

Question 16

Q

Dijstra, which graphs can it handle?

Answer

A

Directed or undirected graphs with non-negative weights.

Question 17

Q

Dijstra, which problem can it solve?

Answer

A

Finding the shortest paths from source s to all vertices.

Question 18

Q

_Dijstra, write exactly the Relax(u,v,w(u,v)) procedure_

Question 19

Q

Dijstra, show me the initilization step.

You are given G=(V,E),s,w

Question 20

Q

Dijstra, what is the loop step in the algorithm?

Question 21

Q

How is Dijkstra’s algorithm implemented?

what’s his run-time? divide it to operation on Q and operations on the array d

Answer

A

Q is maintained by a minimum heap in which d(v) is a key.*
we push mininum d(v) from Q using ExtractMin.*
1. Q*
Initilization of Q - O(|V|)
There are exactly |V| Extract-Min operations.
There are at most |E| Relax operations, which decreases the value of d(v). This implies O(|E|) decrease-key(v) operations (log(|V|)). In total - O(|E|log|V|).

d

Initializing d and s - O(|V|)
|E| Relax operations on d(v), each O(1). O(|E|)
In total: O(|E|+|V|).

In total: O(|E| log|V|)

Question 22

Q

Dijkstra, what is the lower bound claim?

Answer

A

d(v)>=delta(s,v)

That is, d(v) is always greater equal to the value of the lightest path.

Question 23

Q

Dijkstra, What is the correctness statement?

Answer

A

When the algorithm is done, for all v, d(v)=delta(s,v)

Question 24

Q

Dijkstra, which observation is used in the proof?*
Explain it.*

Answer

A

Once vertex u is being added to S, d(u) does not change.

Explanation:

After u is being added to S, we execute Relax operation on vertex v from U, which share an edge with u. The updated value is d(v), and is again, is not chosen from S.

Question 25

Q

Dijkstra, what is the first claim?

Answer

A

Claim 1:

After Relax(u,v), d(v)<= d(u)+w(u,v) is satisfied through all the remaining steps of the algorithm.

Question 26

Q

Diskjstra, what is the proof for the first claim?

Answer

A

By the end of Relax(u,v):

d(v)=min{d(v),d(u)+w(u),v} is satisfied.
- That is, d(v)<= d(u)+w(u,v)
Relax is performed due to the insertion of u into S.
According to the observation: d(u) will not further change.
In contrast, d(v) might change, but only decrease, so the inequality holds.

Question 27

Q

Dijkstra, what is the helping statement?

Answer

A

When vertex u is being added to S d(u)=delta(s,u) is satisfied.

That is, d(u) holds the value for the lightest path

Question 28

Q

Dijkstra, what is the proof for the correctness statement?

Answer

A

Proof of the correctness statement

In each step a vertex shifts from Q to S
- After |V| iterations, S=V and the algorithm stops.
By the helping statement, when vertex u enters S:
- d(u) = delta(s,u)
- By the observation, this value does not change.

Question 29

Q

Dijkstra, what is the proof for the helping statement?

Answer

A

We prove using induction on the algorithm steps - i:

basis i = 1. when u=s.
- d(u) = 0
- delta(s,s) = 0
Induction assumption:
- after i-1 iterations, for all u in S, d(u)=delta(s,u)
step:
- let u be that ith vertex chosed to enter S
- Assume u is accessible from S.
- Let Psu be some lightest path from s to u.
- Let (x,y) be an edge in Psu, x in S, y in U.
  - Psx is Reisha of lightest path
    - w(Psx) = delta(s,x).
  - for x in S, the induction assumption holds
    - d(x) = delta(s,x)
  - w(Pyu)=>0
    - because lights are non-negative
  - by claim 1 on (x,y):
    - d(y)<=d(x)+w(x,y)
  - The algoirthm choose u in this step thus:
    - d(y)>=d(u)
  - In total:

delta(s,u) = w(Psu) = w(Psx) + w(x,y) + w(Pyu)

w(Psx) + w(x,y) + w(Pyu) = delta(s,x)+w(x,y)+w(Pyu)*
delta(s,x)+w(x,y)+w(Pyu) = d(x) + w(x,y) + w(Pyu)*
d(x) + w(x,y) + w(Pyu) >= d(x)+w(x,y)>= d(y) >= d(u)*

Question 30

Q

What is the bottle neck problem?

Answer

A

Definition:

For source vertex s and vertex u:
- bottle neck in path P is:
  - w(minimal edge in P)
- B(s,u):
  - B(s,s) = infinity
  - Largest bottle neck within all paths from s to u
  - If no such path exists - minus infinity

The problem:

Input: weighted graph G=(V,E,w) and source vertex s
Find B(S,u) for every u in V.

Question 31

Q

bottle neck problem:*
explain BRelax(u,v,w)

Answer

A

BRelxa(u,v,w):

There’s an edge between u and v
b[v] - current largest bottle neck from s to u.
Check if there’s a path s to u with a larger bottle neck:
- if b[v]
- b[v] = min{b[u],w(u,v)}

Question 32

Q

BottleNeck(G, w, s)*
Explain the initialization step.*

Question 33

Q

BottleNeck(G, w, s)*
Explain the loop step.*

Question 34

Q

BottleNack

What is the main statement?
what is claim 1?
what is claim 2?
what is the observation?

Question 35

Q

In the proof of the correntness statement there are three cases we need to check.

What are they?

Answer

A

We need to prove that for any vertex u, the moment it enters S, b[u]=B(s,u) is satisfied.*
Note: by the observation this equality hold until the end of the run.*

Cases to check:

u=s
No path from s to u
There’s a path from s to u, and u is not s.

Question 36

Q

BottleNeck corretness statement proof*
How is the first case proved?*

Answer

A

s = u.

We set b[s] = infinity at the initialization step.
s is the first to enter S
B(s,s) = infinity by definition.

Question 37

Q

BottleNeck corretness statement proof

How is the second case proved?

Answer

A

There is no path from s to u

B(s,u) = minus infinity
The 2nd claim tells us that b[u]<=B(s,u), always.
b[u] = minus infinity

Question 38

Q

BottleNeck corretness statement proof

Third case:*
it is proved using induction. induction on what?

Answer

A

On the order of removal of vertices from Q

AKA, u = EXTRACT-MAX(Q)

Question 39

Q

BottleNeck corretness statement proof

third case:*
what is the induction proof?

Question 40

Q

BottleNeck, what is the proof for claim 1?

Question 41

Q

BottleNeck, 2nd claim proof.

Recall: 2nd claim

All along the algorithm, for each vertex v, b[v]<=B(s,v) is satisfied.

Question 42

Q

What is the algorithm for the attached problem?*
What is its run-time?*

Question 43

Q

What is the main statement?*
what are the two claims we use?*

Question 44

Q

How is the 1st claim proved?

Question 45

Q

How is the 2nd claim proved?

Answer

A

_Induction on the length of the path i_

Question 46

Q

How is the main statement proved?

Question 47

Q

Which algorithm is designed to find the lightests paths when negative weights are allowed?

Answer

A

Bellman-Ford

Question 48

Q

Describe Bellman-Ford’s algorithm

Question 49

Q

Analyze Bellman-Ford run-time

Question 50

Q

Bellman-Ford*
Assume all vertices are accessible from s*
We can run first BFS to identify the unaccessible vertices and avoid them.*
Theorem:
There exists a lightest path from s to v, for all v in V, if and only if there is no path from s to v which contains a circle of negative weight.*

Prove the theorem