Lesson test: Shortest paths and spanning trees

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Shortest paths and spanning trees

1.[2p]
What does relaxing the edge $(u, v)$ of weight $w$ do?

If $d [u] + w < d [v]$ , it lowers $d [v]$ to $d [u] + w$ and records $u$ as $v$ 's predecessor

Correct

It removes the edge from the graph

The answer is: If $d [u] + w < d [v]$ , it lowers $d [v]$ to $d [u] + w$ and records $u$ as $v$ 's predecessor

It sets $d [v]$ to $w$

The answer is: If $d [u] + w < d [v]$ , it lowers $d [v]$ to $d [u] + w$ and records $u$ as $v$ 's predecessor

It marks $v$ as settled

The answer is: If $d [u] + w < d [v]$ , it lowers $d [v]$ to $d [u] + w$ and records $u$ as $v$ 's predecessor

2.[3p]
In the undirected graph with edges AB 4, AC 2, BC 1, BD 5, CD 8, CE 10, DE 2, DF 6, EF 3, what is the shortest distance from A to F?

CorrectNot quite: 13

3.[2p]
In that same graph, what is the shortest distance from A to D?

CorrectNot quite: 8

4.[3p]
Dijkstra's correctness argument fails with a negative edge because

it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks

Correct

the priority queue cannot hold negative keys

The answer is: it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks

the graph might then be disconnected

The answer is: it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks

relaxation would never terminate

The answer is: it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks

5.[2p]
Adding a large constant to every edge weight makes a graph with negative edges safe for Dijkstra.

True

The answer is: False

False

Correct

6.[2p]
Bellman-Ford makes $V - 1$ passes over the whole edge set. On a graph with 50 vertices and 200 edges, how many edge relaxations is that?

CorrectNot quite: 9800

7.[3p]
Run Kruskal on the graph with edges PQ 7, PR 5, QR 8, QS 9, RS 15, RT 6, ST 8, SU 5, TU 11. What is the total weight of the minimum spanning tree?

CorrectNot quite: 31

8.[3p]
The cut property says that

the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree

Correct

every minimum spanning tree contains the globally cheapest edge only

The answer is: the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree

a spanning tree has exactly $V$ edges

The answer is: the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree

removing an edge from a cycle disconnects the graph

The answer is: the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree

9.[3p]
Match each algorithm to what it takes at each step.

Dijkstra
Prim
Kruskal
Bellman-Ford

the vertex with the smallest distance estimate
the cheapest edge leaving the tree so far
no choice at all, every edge each pass
the cheapest remaining edge joining two components

Show the answer

Dijkstra: the vertex with the smallest distance estimate Prim: the cheapest edge leaving the tree so far Kruskal: the cheapest remaining edge joining two components Bellman-Ford: no choice at all, every edge each pass

1.[2p] What does relaxing the edge (u,v) of weight w do?

2.[3p] In the undirected graph with edges AB 4, AC 2, BC 1, BD 5, CD 8, CE 10, DE 2, DF 6, EF 3, what is the shortest distance from A to F?

3.[2p] In that same graph, what is the shortest distance from A to D?

4.[3p] Dijkstra's correctness argument fails with a negative edge because

5.[2p] Adding a large constant to every edge weight makes a graph with negative edges safe for Dijkstra.

6.[2p] Bellman-Ford makes V−1 passes over the whole edge set. On a graph with 50 vertices and 200 edges, how many edge relaxations is that?

7.[3p] Run Kruskal on the graph with edges PQ 7, PR 5, QR 8, QS 9, RS 15, RT 6, ST 8, SU 5, TU 11. What is the total weight of the minimum spanning tree?

8.[3p] The cut property says that

9.[3p] Match each algorithm to what it takes at each step.

1.[2p]
What does relaxing the edge $(u, v)$ of weight $w$ do?

2.[3p]
In the undirected graph with edges AB 4, AC 2, BC 1, BD 5, CD 8, CE 10, DE 2, DF 6, EF 3, what is the shortest distance from A to F?

3.[2p]
In that same graph, what is the shortest distance from A to D?

4.[3p]
Dijkstra's correctness argument fails with a negative edge because

5.[2p]
Adding a large constant to every edge weight makes a graph with negative edges safe for Dijkstra.

6.[2p]
Bellman-Ford makes $V - 1$ passes over the whole edge set. On a graph with 50 vertices and 200 edges, how many edge relaxations is that?

7.[3p]
Run Kruskal on the graph with edges PQ 7, PR 5, QR 8, QS 9, RS 15, RT 6, ST 8, SU 5, TU 11. What is the total weight of the minimum spanning tree?

8.[3p]
The cut property says that

9.[3p]
Match each algorithm to what it takes at each step.