hop
One step along an edge; a path's hop count is how many edges it crosses, ignoring any weights.
In more detail
BFS finds paths with the fewest hops, such as the degrees of separation between two people in a social network. When edges have different weights, fewest hops is not the same as cheapest, and Dijkstra's algorithm is needed.
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.
- 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.
- unweighted graph — A graph whose edges carry no weights, so every edge counts the same.
Taught in
- 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