Comprehensive and Detailed Explanation From Exact Extract:
Dijkstra’s shortest path algorithm finds the shortest path between nodes in a weighted graph, often used for navigation or network routing. According to foundational programming principles (e.g., Certiport Scripting and Programming Foundations Study Guide, Section on Algorithms), it is designed for problems involving optimal paths in graphs with non-negative edge weights.
Option A: "Given an increasing array of numbers, is the number 19 in the array?" This is incorrect. This is a search problem, typically solved by binary search for a sorted array, not Dijkstra’s algorithm, which deals with graphs.
Option B: "Given an alphabetized list of race entrants and a person’s name, is the person entered in the race?" This is incorrect. This is another search problem, solvable by binary search or linear search, not related to graph paths.
Option C: "Given two newspaper articles, what is the greatest sequence of words shared by both articles?" This is incorrect. This is a longest common subsequence (LCS) problem, solved by dynamic programming, not Dijkstra’s algorithm.
Option D: "Given the coordinates of five positions, what is the most fuel-efficient flight path?" This is correct. This describes a shortest path problem in a graph where nodes are positions (coordinates) and edges are distances or fuel costs. Dijkstra’s algorithm can find the most efficient path (e.g., minimizing fuel) between these points, assuming non-negative weights.
Certiport Scripting and Programming Foundations Study Guide (Section on Algorithms).
Cormen, T.H., et al., Introduction to Algorithms, 3rd Edition (Dijkstra’s Algorithm, Chapter 24).
GeeksforGeeks: “Dijkstra’s Shortest Path Algorithm” (https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/).
Submit