Q.1 Which of the following algorithms is commonly used to find the shortest path in a graph with non-negative edge weights?
Bellman-Ford Algorithm
Dijkstra's Algorithm
Prim's Algorithm
Kruskal's Algorithm
Explanation - Dijkstra's algorithm works efficiently on graphs with non-negative edge weights to find the shortest path.
Correct answer is: Dijkstra's Algorithm
Q.2 What is the time complexity of Dijkstra’s algorithm using a priority queue and adjacency list?
O(V^2)
O(E log V)
O(V log E)
O(VE)
Explanation - Using a min-heap priority queue with adjacency list, Dijkstra runs in O(E log V).
Correct answer is: O(E log V)
Q.3 Which algorithm can handle graphs with negative edge weights but no negative cycles?
Dijkstra's Algorithm
Prim's Algorithm
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
Explanation - Bellman-Ford can handle negative weights, unlike Dijkstra. However, it fails if negative weight cycles exist.
Correct answer is: Bellman-Ford Algorithm
Q.4 Floyd-Warshall algorithm is used for:
Single-source shortest path
All-pairs shortest path
Minimum spanning tree
Topological sorting
Explanation - Floyd-Warshall computes shortest paths between all pairs of vertices.
Correct answer is: All-pairs shortest path
Q.5 What is the time complexity of Bellman-Ford algorithm?
O(V^2)
O(VE)
O(E log V)
O(V^3)
Explanation - Bellman-Ford relaxes all edges up to V-1 times, leading to O(VE) time complexity.
Correct answer is: O(VE)
Q.6 Which algorithm can detect negative weight cycles?
Dijkstra's Algorithm
Bellman-Ford Algorithm
Prim's Algorithm
Kruskal's Algorithm
Explanation - Bellman-Ford detects negative cycles by performing one more relaxation step after V-1 iterations.
Correct answer is: Bellman-Ford Algorithm
Q.7 Johnson’s algorithm is useful for:
Minimum spanning tree
All-pairs shortest path
Network flow
Topological sorting
Explanation - Johnson’s algorithm efficiently computes all-pairs shortest paths, especially in sparse graphs.
Correct answer is: All-pairs shortest path
Q.8 The shortest path problem in graphs with negative weight cycles is:
Solvable with Bellman-Ford
Solvable with Floyd-Warshall
Unsolvable
Solvable with Dijkstra
Explanation - If negative cycles exist, shortest paths are undefined because you can loop infinitely to reduce cost.
Correct answer is: Unsolvable
Q.9 What data structure is typically used in Dijkstra’s algorithm for efficient implementation?
Stack
Queue
Priority Queue (Heap)
Hash Table
Explanation - A min-priority queue helps efficiently extract the vertex with minimum distance in Dijkstra’s algorithm.
Correct answer is: Priority Queue (Heap)
Q.10 Floyd-Warshall algorithm works in which time complexity?
O(VE)
O(V^3)
O(E log V)
O(V^2)
Explanation - Floyd-Warshall performs three nested loops, leading to O(V^3) complexity.
Correct answer is: O(V^3)
Q.11 Which algorithm is more suitable for sparse graphs for single-source shortest path?
Dijkstra’s Algorithm
Floyd-Warshall Algorithm
Bellman-Ford Algorithm
Johnson’s Algorithm
Explanation - For sparse graphs, Dijkstra with a priority queue is very efficient.
Correct answer is: Dijkstra’s Algorithm
Q.12 The relaxation step in shortest path algorithms involves:
Increasing edge weights
Decreasing edge weights
Updating distance estimates
Sorting edges
Explanation - Relaxation checks if the current path offers a shorter distance and updates accordingly.
Correct answer is: Updating distance estimates
Q.13 Which algorithm is guaranteed to find the shortest path in an unweighted graph?
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Breadth-First Search
Depth-First Search
Explanation - BFS explores layer by layer, ensuring shortest paths in unweighted graphs.
Correct answer is: Breadth-First Search
Q.14 In Dijkstra’s algorithm, what happens if the graph contains a negative edge weight?
It still works correctly
It gives incorrect results
It runs faster
It detects cycles
Explanation - Dijkstra assumes non-negative edge weights. Negative edges break its correctness.
Correct answer is: It gives incorrect results
Q.15 Which of the following is an application of shortest path algorithms?
Network routing
Sorting numbers
Database indexing
Pattern matching
Explanation - Shortest path algorithms are crucial for efficient data routing in networks.
Correct answer is: Network routing
Q.16 Which algorithm uses dynamic programming to solve all-pairs shortest path?
Bellman-Ford
Dijkstra
Floyd-Warshall
Prim’s Algorithm
Explanation - Floyd-Warshall applies dynamic programming principles to compute shortest paths.
Correct answer is: Floyd-Warshall
Q.17 What is the output of Bellman-Ford if a negative cycle is detected?
Infinity distances
Error/Warning
Correct shortest path
Random values
Explanation - Bellman-Ford typically signals an error if negative cycles exist.
Correct answer is: Error/Warning
Q.18 Which algorithm combines reweighting with Dijkstra’s algorithm?
Johnson’s Algorithm
Bellman-Ford
Floyd-Warshall
Prim’s Algorithm
Explanation - Johnson’s algorithm uses Bellman-Ford for reweighting and then applies Dijkstra.
Correct answer is: Johnson’s Algorithm
Q.19 In Dijkstra’s algorithm, the initial distance to all vertices except the source is:
1
0
Infinity
Negative
Explanation - All distances start as infinity except the source which is 0.
Correct answer is: Infinity
Q.20 Which shortest path algorithm is most suitable for dense graphs?
Bellman-Ford
Dijkstra
Floyd-Warshall
BFS
Explanation - Floyd-Warshall’s O(V^3) complexity suits dense graphs better than sparse.
Correct answer is: Floyd-Warshall
Q.21 The Bellman-Ford algorithm relaxes edges how many times?
V
E
V-1
E-1
Explanation - It performs V-1 iterations of relaxation for correctness.
Correct answer is: V-1
Q.22 What happens in Dijkstra’s algorithm after a vertex is marked as 'visited'?
Its distance can still change
Its distance is finalized
It is removed from graph
It is ignored forever
Explanation - Once a node is visited, its shortest path distance is finalized in Dijkstra.
Correct answer is: Its distance is finalized
Q.23 What is the space complexity of Floyd-Warshall algorithm?
O(V)
O(E)
O(V^2)
O(V^3)
Explanation - Floyd-Warshall stores distance matrix of size VxV, hence O(V^2) space.
Correct answer is: O(V^2)
Q.24 Which algorithm is based on repeatedly relaxing edges until convergence?
Dijkstra
Bellman-Ford
Prim’s
Kruskal’s
Explanation - Bellman-Ford works by repeatedly relaxing edges.
Correct answer is: Bellman-Ford