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

Shortest paths and spanning trees

1.[2p]

What does relaxing the edge (u,v) of weight w do?

Correct
The answer is: If $d[u] + w < d[v]$, it lowers $d[v]$ to $d[u] + w$ and records $u$ as $v$'s predecessor
The answer is: If $d[u] + w < d[v]$, it lowers $d[v]$ to $d[u] + w$ and records $u$ as $v$'s predecessor
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

Correct
The answer is: it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks
The answer is: it assumes the prefix of a path is no longer than the whole path, which a negative edge breaks
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.

The answer is: 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

Correct
The answer is: the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree
The answer is: the cheapest edge crossing any split of the vertices into two parts belongs to some minimum spanning tree
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