shortest path
The path between two vertices with the smallest total length: fewest edges in an unweighted graph, lowest total weight in a weighted one.
In more detail
BFS finds shortest paths by hops; Dijkstra's algorithm by weight when no weight is negative; Bellman-Ford handles negative weights. Each keeps a distance map from every vertex to its best known distance from the source.
Related terms
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- Bellman-Ford algorithm — A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.
- parent map — A dict recording, for each vertex a search reaches, the vertex it was reached from, so the path can be rebuilt afterwards.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers