27.1. Design and Analysis of Algorithms, Chennai

Try these first

1. 1.

   What is Dijkstra's algorithm used for?

   Hint

   Think about shortest path problems.

2. 2.

   What is the initial distance of all vertices at the start of Dijkstra's algorithm?

   Hint

   Consider what we do before starting the pathfinding.

3. 3.

   What is the time complexity of Dijkstra's algorithm when using an adjacency matrix?

   • O(n)
   • O(n log n)
   • O(n^2)
   • O(m + n)

   Hint

   Consider how many vertices you need to scan.

4. 4.

   Dijkstra's algorithm can handle negative edge weights appropriately.

   • True
   • False

   Hint

   Think about the implications of negative weights on distance calculations.

5. 5.

   Given a graph with vertices labeled A to E, and weights as follows: A-B: 1, A-C: 5, B-C: 2, B-D: 4, C-D: 1, C-E: 3, D-E: 2. Determine the shortest path from A to E using Dijkstra's algorithm.

   Hint

   Draw the graph and systematically calculate distances while burning vertices.

6. 6.

   Create a graph with at least one negative edge but without a negative cycle. Apply Dijkstra's algorithm and explain the outcome.

   Hint

   Define distances carefully to see where the pitfalls are.