27.1.3. Department of Computer Science and Engineering

Try these first

1. 1.

   What does Dijkstra's algorithm accomplish?

   Hint

   Think about applications like navigation.

2. 2.

   What is initialized to infinity in Dijkstra's algorithm?

   Hint

   Consider the starting point's significance.

3. 3.

   What technique does Dijkstra's algorithm use to determine the shortest path?

   • Dynamic Programming
   • Greedy Strategy
   • Brute Force

   Hint

   Think about how Dijkstra prioritizes its choices.

4. 4.

   True or False: Dijkstra's algorithm can handle graphs with negative edge weights.

   • True
   • False

   Hint

   Consider why the local choices might fail.

5. 5.

   Given a graph with both positive and negative weights but no negative cycles, apply Dijkstra's algorithm and explain the steps taken.

   Hint

   Remember to keep track of updates on distances based on the edges from the burnt vertices.

6. 6.

   Critique the utility of Dijkstra’s algorithm in real-world applications that involve routes with varied constraints such as tolls (negative weights).

   Hint

   Consider examples where negative weights could change the optimal path drastically.