SCRIPTING-AND-PROGRAMMING-FOUNDATIONS practice question 17 of 25

Which problem is solved by Dijkstra’s shortest path algorithm?

Full set: 137 questions
Answer options
A: Given an increasing array of numbers, is the number 19 in the array?
B: Given an alphabetized list of race entrants and a person’s name, is the person entered in the race?
C: Given two newspaper articles, what is the greatest sequence of words shared by both articles?
D: Given the coordinates of five positions, what is the most fuel-efficient flight path? Correct answer
Correct Answer:
D. Given the coordinates of five positions, what is the most fuel-efficient flight path?
Explanation

Dijkstra's algorithm is a fundamental graph theory algorithm used to find the shortest paths between nodes in a weighted graph with non-negative edge weights. A flight path problem is a classic application, where geographical positions are nodes (vertices) and the fuel cost or distance between them represents the weighted edges. The algorithm's purpose is to find the path with the minimum cumulative weight, which corresponds to the most fuel-efficient route.

Why Incorrect

A: This is a search problem in a sorted array, which is most efficiently solved using a binary search algorithm. B: This is also a search problem. Given an alphabetized (sorted) list, a binary search is the appropriate algorithm. C: This is the "longest common subsequence" problem, which is typically solved using dynamic programming, not a shortest path algorithm.

References

- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 24.3, "Dijkstra's algorithm," details its operation for solving single-source shortest-path problems on weighted, directed graphs.

- MIT OpenCourseWare. (2011). 6.006 Introduction to Algorithms, Fall 2011. Lecture 16: Dijkstra. The lecture describes the algorithm and its application to real-world problems like finding the shortest route in a road network.

- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390. This is the original academic paper that introduced the algorithm.

Scroll to Top