[prev] 57 [next]

Shortest Path

Path = sequence of edges in graph G    p = (v0,v1), (v1,v2), …, (vm-1,vm)

cost(path) = sum of edge weights along path

Shortest path between vertices s and t

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

Finding shortest path between two given nodes known as source-target SP problem

Variations: single-source SP, all-pairs SP

Applications:  navigation,  routing in data networks,  …