27.2.3. Handling Negative Edges

Try these first

1. 1.

   What is the primary function of Dijkstra's algorithm?

   Hint

   Think about pathfinding in graphs.

2. 2.

   Define a burnt vertex.

   Hint

   Consider this as a confirmed choice in optimization.

3. 3.

   What type of algorithm is Dijkstra's?

   • Dynamic Programming
   • Greedy
   • Divide and Conquer

   Hint

   Remember the type of choices made in Dijkstra's strategy.

4. 4.

   True or False: Dijkstra’s algorithm can find shortest paths in graphs with negative cycles.

   • True
   • False

   Hint

   Consider the definition of a shortest path in terms of weights.

5. 5.

   You are given a graph with a negative cycle. Formulate how you would approach finding the shortest path from a source vertex to a destination vertex. Discuss the potential outcomes.

   Hint

   Consider what happens in the presence of repeating paths.

6. 6.

   Construct a graph with negative edges and no negative cycle. Use the Bellman-Ford algorithm to determine the shortest paths and explain your findings.

   Hint

   Reflect on how negative edges might still lead to a valid optimal path.