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