27.1.1. Mathematical Institute

Try these first

1. 1.

   What algorithm is used to find the shortest path in a graph with non-negative weights?

   Hint

   Think about algorithms for graph traversal.

2. 2.

   What do you set the source vertex distance to at the beginning of Dijkstra's algorithm?

   Hint

   It reflects the start point in terms of distance.

3. 3.

   What is the primary function of Dijkstra's Algorithm?

   • Finding the longest path
   • Finding shortest paths
   • Sorting vertices

   Hint

   Focus on the word 'shortest' in pathfinding.

4. 4.

   Dijkstra's Algorithm works best with which type of graph?

   • True
   • False

   Hint

   Consider the assumptions of the algorithm.

5. 5.

   Given a graph with vertices A, B, C, and D, with edges AB (1), AC (4), BD (3), and CD (2), apply Dijkstra's algorithm starting from A. What is the shortest path to D?

   Hint

   Remember to track the distances and choose the least costly path at each step.

6. 6.

   Consider a graph with a negative edge weight. Explain how this could alter the results of Dijkstra's algorithm and suggest an alternative algorithm that can handle such a case.

   Hint

   Think about what happens when a vertex is burnt and how negative cycles can influence overall costs.