26.1.7.2. Formal Algorithm Description

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about graphs with varying edge costs.

2. 2.

   What does Dijkstra's Algorithm do?

   Hint

   Recall the fire spreading analogy.

3. 3.

   What is the primary objective of Dijkstra's Algorithm?

   • To find the longest path
   • To find the shortest path from a single source
   • To connect all vertices

   Hint

   Focus on the term 'shortest path'.

4. 4.

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

   • True
   • False

   Hint

   Remember how weights work in the algorithm.

5. 5.

   Given a graph with vertices A, B, C, and D, and edges with weights between them, find the shortest path from A to D using Dijkstra's algorithm.

   Hint

   Don't forget to update the neighbors' costs after visiting a vertex.

6. 6.

   Explain why Dijkstra's algorithm fails with negatively weighted edges, and provide an example.

   Hint

   Consider paths that could 'get shorter' after visiting them.