Dijkstra algorithm, which solves the single-source shortest--paths problem, is…
2014
Dijkstra algorithm, which solves the single-source shortest--paths problem, is a _________, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a _________
- A.
Greedy algorithm, Divide-conquer algorithm
- B.
Divide-conquer algorithm, Greedy algorithm
- C.
Greedy algorithm, Dynamic programming algorithm
- D.
Dynamic programming algorithm, Greedy algorithm
Attempted by 222 students.
Show answer & explanation
Correct answer: C
Answer: Dijkstra is a greedy algorithm, and Floyd–Warshall is a dynamic programming algorithm.
Key points:
Dijkstra (single-source shortest paths): greedy — it repeatedly selects the nearest unvisited vertex and relaxes its outgoing edges. It requires non-negative edge weights. Typical time complexity is O(V^2) for a simple implementation or O(E + V log V) with a priority queue.
Floyd–Warshall (all-pairs shortest paths): dynamic programming — it computes shortest paths by considering intermediate vertices one by one and updating distances using the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Time complexity is O(V^3).
Therefore: Dijkstra = greedy single-source algorithm; Floyd–Warshall = dynamic programming all-pairs algorithm.