A weighted graph assigns a numerical weight to each edge.

For a path

$$v_0\to v_1\to\cdots\to v_k,$$

its total cost is commonly defined as the sum of its edge weights:

$$w(P)=\sum_{i=0}^{k-1} w(v_i,v_{i+1}).$$

Weights can represent distance, time, price, risk or any additive transition cost.

A shortest path between two vertices is a path with minimum total weight among all allowed paths connecting them.

Negative edge weights change the problem substantially: an algorithm that assumes extending a path can only increase its cost may become invalid. A reachable negative-weight cycle can make the notion of a finite shortest path undefined, because looping around the cycle repeatedly decreases the total cost.