SCRIPTING-AND-PROGRAMMING-FOUNDATIONS practice question 17 of 25
Which problem is solved by Dijkstra’s shortest path algorithm?
Full set: 137 questionsDijkstra'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.
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.
- 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.
Keep practicing
Take the free SCRIPTING-AND-PROGRAMMING-FOUNDATIONS practice test
Ten exam-style questions with answers and explanations, plus the exam facts and study guides.
More questions
Other SCRIPTING-AND-PROGRAMMING-FOUNDATIONS practice questions
- Question 1Which characteristic distinguishes a markup language from other languages?
- Question 2A program calculates the average miles per gallon given miles traveled and gas consumed H…
- Question 5Which characteristic specifically describes an object-oriented language?
- Question 6Which is one characteristic of an object-oriented language that is not a characteristic o…
- Question 7Which operation should be used to check if the difference of two values is greater than 1?
- Question 9A program allows the user to play a game. At the end of each game, the program asks the u…
