Dijkstra's algorithm in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of Dijkstra's algorithm

What is the main goal of Dijkstra's algorithm in graph theory?

A To find the shortest path from a starting node to all other nodes in a graph with non-negative edge weights.

B To find the longest path between two nodes in any graph.

C To detect cycles in a directed graph.

D To sort the nodes of a graph in topological order.

💡 Hint

Think about what kind of paths Dijkstra's algorithm helps to find and what restrictions it has on edge weights.

Dijkstra's algorithm is designed to find the shortest paths from a single starting node to all other nodes in a graph where all edge weights are zero or positive. It does not work correctly with negative edge weights.

📋 Factual

intermediate

Dijkstra's algorithm and negative edge weights

What happens if Dijkstra's algorithm is applied to a graph that contains negative edge weights?

A It will run infinitely without stopping.

B It will always find the correct shortest paths regardless of edge weights.

C It will detect the negative edges and remove them automatically.

D It may produce incorrect shortest path results because it assumes all edge weights are non-negative.

💡 Hint

Consider the assumptions Dijkstra's algorithm makes about edge weights and how negative weights affect path calculations.

Dijkstra's algorithm assumes all edge weights are non-negative. If negative weights exist, the algorithm can incorrectly calculate shortest paths because it does not revisit nodes once visited, missing shorter paths through negative edges.

🚀 Application

advanced

Output of Dijkstra's algorithm on a weighted graph

Given the following weighted graph edges:

A-B: 4, A-C: 2, B-C: 5, B-D: 10, C-D: 3, D-E: 1, E-F: 2, F-D: 6

What is the shortest distance from node A to node E using Dijkstra's algorithm?

A 6

B 9

C 8

D 7

💡 Hint

Trace the shortest path step-by-step from A to E considering the edge weights.

The shortest path from A to E is A -> C -> D -> E with distances 2 + 3 + 1 = 6. However, the total distance is 6, but option A is 7, so let's re-check carefully.

Paths:

• A-C (2), C-D (3), D-E (1) = 6
• A-B (4), B-D (10), D-E (1) = 15
• A-C (2), C-B (5), B-D (10), D-E (1) = 18

So the shortest distance is 6, which matches option A, but option A is 6, option A is 7. So correct answer is A.

🔍 Analysis

advanced

Time complexity of Dijkstra's algorithm

Which of the following best describes the time complexity of Dijkstra's algorithm when implemented with a binary heap priority queue on a graph with V vertices and E edges?

A O(V + E log V)

B O(V^2)

C O(E + V log V)

D O(V log E)

💡 Hint

Consider how the priority queue operations affect the complexity and how many edges and vertices are processed.

Using a binary heap, Dijkstra's algorithm runs in O((V + E) log V) time because each vertex is inserted into the priority queue once and each edge is relaxed once.

❓ Reasoning

expert

Choosing the correct data structure for Dijkstra's algorithm

Why is a priority queue (min-heap) preferred over a simple queue when implementing Dijkstra's algorithm?

A Because it allows random access to nodes, speeding up the algorithm.

B Because it always selects the next node with the smallest tentative distance, ensuring correct shortest path calculation.

C Because it stores nodes in the order they were discovered, which is necessary for breadth-first search.

D Because it automatically removes cycles from the graph.

💡 Hint

Think about how Dijkstra's algorithm decides which node to explore next.

Dijkstra's algorithm relies on always choosing the node with the smallest current distance to ensure the shortest paths are found. A priority queue efficiently supports this by quickly retrieving the minimum-distance node.