Recipe

Compute a path's weight

Use when: you're given a specific path through a weighted graph and need its total cost, or you're comparing two candidate paths to see which is actually shorter

Goal: the path's total weight, and confirmation that fewer edges doesn't automatically mean less weight

Taught in Weighted graphs, revisited

1. 1

   Write down every edge the path uses, in the order it's traveled, from the vertex sequence given.

   Example

   The path S \to A \to C \to T uses edges S\text{-}A, A\text{-}C, C\text{-}T -- three edges, not two.

   Why: the weight of a path is a sum over its edges, so the edges have to be identified before anything can be added.

2. 2

   Look up w(u,v) for every edge on the list, not the number of edges.

   Example

   w(S,A)=2, w(A,C)=2, w(C,T)=2.

   Why: confusing "how many edges" with "how much do they cost" is the single most common shortest-path mistake -- the two questions have different answers whenever weights differ.

3. 3

   Add every edge weight collected in the step above. The total is the path's weight -- compare it against any other candidate path's total the same way, never by comparing edge counts.

   Example

   2+2+2=6 for the three-edge path; a competing two-edge path with weights 1 and 8 sums to 9 -- the three-edge path is actually cheaper.

   • every edge weight equals 1 — total weight equals edge count, so BFS (Chapter 4) already gives the right answer with no further work needed
   • weights differ — BFS's edge-counting no longer tracks total cost, and this chapter's algorithms are required

   Why: the shortest-path problem asks for minimum total weight, not minimum edge count, and the two coincide only in the special case every weight equals 1.