Wk 7/8 : SSSP, BF, Dijkstra, APSP, FW, Trans. Closure

Question 1

Can a shortest path have cycles? Why not?

Answer 1

If you find an SSSP with a cycle, and remove it, you still have a source to definition and the total weight is less.

Question 2

How does the single-source-shortest-path problem relate to its cousins? (what are its cousins?)

Answer 2

single-destination (SSSP in opposite direction this would be a column in the matrix)
single-pair (this is a single entry in the matrix, it is already solved when SSSP is run, and its not any faster)
all-pairs shortest path (this is finding every value in the matrix, in other words all the rows and all the columns, therefore also all the pairs/points as well) You don’t need to run SSSP from each vertex to find this, we can do it quicker.

single source finds a row in the matrix.

Question 3

What is the optimal sub-structure of a shortest path mean?

Answer 3

Every sub-path of a SSSP is also a SSSP. This is what connects this to dynamic programming and the greedy method.

Question 4

What is the relationship between negative weight cycles and the shortest path algorithms?

Answer 4

shortest path is not defined for a graph that has negative weight cycles, because any shortest path would continually go round and round that cycle and get -INF weight

Question 5

What is the main difference between Dijkstra and Bellman-Ford with regard to assumptions?

Answer 5

Bellman-Ford can handle negative weight edges but is slower. Dijkstra takes advantage of the assumption that if there are no negative edge weights and runs faster than Bellman-Ford.

Question 6

How do we track the actual shortest path found by the algorithm?

Answer 6

With predecessor pointers and Shortest-Path trees.

Question 7

What is the general format for all the algorithms in this chapter? (BF and Dijk)

Answer 7

Initialize the d values and pointers of every node, then repeatedly “relax” the deges until we have the shortest path

Question 8

How does Bellman-Ford return whether or not there are negative weight cycles in the graph?

Answer 8

After it runs to get the shortest path, it runs one more time and if the weights decrease again, then we know there’s a negative cycle somewhere.

Question 9

What is the main data structure of Dijkstra’s algorithm? Why?

Answer 9

Priority Queue…

[INSERT]

Question 10

How does Dijkstra use the assumption of no negative edge weights in its advantage?

Answer 10

[INSERT]

Question 11

What are the similarities between Dijkstra and Primm? What are the differences?

Answer 11

[INSERT]

Question 12

Why is Dijkstra considered to be a greedy algorithm?

Answer 12

Each time through its loop it pulls the current lowest value vertex from the priority queue to add to the set S which is the growing SSSP.

Question 13

Prove that the u that comes off the priority queue in Dijkstra is in fact the SP….

Answer 13

[INSERT]

Question 14

How is Dijkstra similar to both Primm and BFS?

Answer 14

Single source shortest path algorithms (Dijkstra) are just BFS with different data structures. Dijkstra uses a priority queue. BFS only used a standard queue. Primm used priority queue as well.

Question 15

How many times do we have to run the EXTEND SHORTEST PATHS within the SLOW-ALL-PAIRS SHORTEST PATHS algorithm? How about for the FAST?

Answer 15

We have to do it n-1 times. Once we hit the nth time, the matrix values don’t change. Essentially every edge and every path has been looked at. For the fast, it’s CLG(lg n) because that’s how many times it takes until we’re bigger than n. Book says that all L^m = L^n-1 for all m >= n-1

Question 16

What are the math replacements required to make FAST-APSP equivalent to matrix multiplication?

Answer 16

see note card

Question 17

What is a transitive closure of a graph and how is it different from a standard graph?

Answer 17

Transitive closure is a {V,E} where E instead of having all the edges that exist in the graph has all the paths that exist in the graph.

Question 18

Why would we prefer the Transitive-Closure version algorithm over a FW run with each edge weight set to 1?

Answer 18

Because on most machines, logical operations run faster than arithmetic operations, also, because boolean values are smaller than integer, it likely takes up less space as well

Question 19

How could we use FW to determine the transitive closure of a graph?

Answer 19

set all edges weight to 1 and run FW. Those with a path get d

Question 20

What is dynamic programming?

Answer 20

Using the concept of sub-optimality (think SSSP) we take a small solution and grow it with one extra degree of freedom each time. Previous solutions are look-ups…And each sub-part of the total solution is itself a solution of the smaller problem.

Question 21

What is triangle inequality and why does it matter for SSSP?

Answer 21

If I have a shortest path from s to v. by definition its the shortest way to get there. I can’t go somewhere else and get there in anything less than the same amount of time, likely more.