Shortest Path
noun
say it: “SHOR-tist PATH” /ˈʃɔrtɪst pæθ/
The route between two points in a graph with the fewest edges or the smallest total weight.
What is a shortest path in a graph?
A shortest path is the best route between two vertices: the one with the fewest edges when every edge counts the same, or the one with the smallest total weight when edges have weights, such as minutes. Breadth-first search finds the first kind; Dijkstra's algorithm finds the second.
In a sentence
- “The GPS found the shortest path home: two roads and 3 minutes, not the direct road's 4.”
Level: Journeyman · More Data Structures terms at this level
Updated