14 Shortest Path More

Question 1

Dijkstra’s algoirthm

Answer 1

Solves the single source shortest path problem in a weighted graph where all edge weights are non-negative.

Question 2

Bellman-Ford Algorithm

Answer 2

Solves the single-source shortest path problem in a weighted graph with some negative edge weights as long as there are no negative weight cycles.

Can detect if there are any negative weight cycles in the graph.

Question 3

Relaxation

Answer 3

Testing whether we can improve the shortest path to vertice v found so far by going through edge u.

If so, it lowers shortest path estimates and changes predecssors.

Question 4

Bellman-Ford is designed for

Answer 4

Direct Graphs

Question 5

If an undirect graph has no negative weight edges, Bellman-Ford will work, but . . .

Answer 5

Dijkstra’s algorithm will also work and will be faster.

Question 6

Is it easier to find shortest path than in a directed acyclic graph that in a graph with cycles?

Answer 6

Yes.

Key idea that reduces time complexity is to consider vertices in topologically sorted order.

Question 7

Longest path problem

Answer 7

Negate all weight and Find shortest path.
Negate Results
Complexity is O(V+E)

Question 8

Both Dijkstra’s and Bellman ford algorithm are examples of

Answer 8

Dynamic Programming