[prev] [index] [next]

Shortest Path

Path = sequence of edges in graph G

With 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

  • a simple path p where s = first(p), t = last(p)
  • no other simple path q has cost(q) < cost(p)
Assumptions: weighted digraph, no negative weights.

Variations: source-target, single-source, all-pairs

Applications:  robot navigation,  routing in data networks