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

Taught in

References