28.2.3. Update Operation in Dijkstra's Algorithm

Try these first

1. 1.

   What does it mean to 'burn' a vertex in Dijkstra's algorithm?

   Hint

   Think of it as locking in the shortest distance.

2. 2.

   What is a negative edge weight?

   Hint

   It's a negative impact on the path length.

3. 3.

   What is the purpose of the update operation in Dijkstra's algorithm?

   • To finalize the shortest distance to a vertex
   • To explore new vertices
   • To reset all distances

   Hint

   Focus on what happens when you burn a vertex.

4. 4.

   True or False: Dijkstra's algorithm effectively calculates shortest paths for graphs with negative edge weights.

   • True
   • False

   Hint

   Consider the implications of negative weights.

5. 5.

   Design a graph with vertices A, B, C, and D, where A to B is 5, A to C is 2, C to D is -4, and what shortest path does Bellman-Ford compute?

   Hint

   Think about how the negative edge affects the overall path.

6. 6.

   Using a weighted directed graph where all edges have positive weights, explain how Dijkstra's algorithm ensures the shortest path is always found.

   Hint

   Focus on the steps and rules of Dijkstra's process.