(W7) Dynamic Programming

Question 1

What does the Bellman-Ford algorithm do that Dijkstras doesn’t?

Answer 1

can calculate the shortest path even if there are negative edge weights

Question 2

What are the 2 key ideas of Bellman-Ford?

Answer 2

Cycles with positive weights won’t be part of the shortest path

Any simple path has at most |V|-1 edges

Question 3

What is the Bellman-Ford Algorithm?

Answer 3

Create a distance and previous array
Mark the starting distance as 0

Iterate over |V|-1 times:
- for each edge (in the whole graph)
- get the updated distance = dist[u] + w(u,v)
- if the distance < distance[v] -> update distance[v] and prev[v] = u

Then - do a final loop check
for each edge in the entire graph
- if distance[u] + w(u,v) < distance[v]
- return an error

Question 4

What is the complexity (time/space) of Bellman-Ford algorithm

Answer 4

Time: O(VE)
Space: O(V)

Question 5

What problem does the Floyd-Warshall problem try and solve?

Answer 5

Compute the shortest distance between any 2 pairs of vertices

Is able to work with negative edge weights

Question 6

What is the Floyd-Warshall Algorithm?

Answer 6

Create an adjacency matrix called dist[][] and preload each edge (u,v) with weight(u,v)

For each vertex k in the graph
- for each pair of vertices (u,v)
if distance[u][k] + distance[k][v] is less than distance[u][v]
- then we have found a shortcut
- distance[u][v] = distance[u][k] + distance[k][v]

Question 7

What is the complexity of Floyd-Warshall?

Answer 7

Time O(V^3) - this should be obvious from the 3x internal loop
Space (V^2) - creating the distance matrix

Question 8

What is the key Floyd-Warshall invariant?

Answer 8

For a graph without negative cycles, after the k-th iteration, the distance[i][j] contains the weight of the shortest path that only uses the intermediate nodes from the set {1,…,k}

Question 9

What properties can you determine about a graph from the Floyd-Warshall distances matrix?

Answer 9

Connectivity - if the distance between u,v is None or Inf - then there is no connecting path

Negative Cycles - if there is any distance[i][i] < 0, then there is a negative cycle

Question 10

What is transitive closure?

Answer 10

It’s a graph G that only contains an edge between (u,v) if there is a path between (u,v) in the main graph

it can be found using the floyd-warshall algorithm