Shortest PathWith unweighted edges, cost(path) = length (#edges) With weighted edges, cost(path) = sum of edge weights (aka weight(path) Shortest path between vertices s and t
Variations: source-target, single-source, all-pairs Applications: robot navigation, routing in data networks |