parent map
A dict recording, for each vertex a search reaches, the vertex it was reached from, so the path can be rebuilt afterwards.
In more detail
To reconstruct a path, start at the destination and follow parents back to the source, then reverse the list. BFS and Dijkstra's algorithm both fill one in as they run.
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.
- 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.
Taught in
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers