A graph having a weight, or number, associated with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc.