Lesson 9

There are many problems that are modeled by weighted graphs, that is, graphs where each edge is assigned a number called a weight. In applications, a weight may mean different things:

• in a road network graph, a weight may mean the distance between two cities or crossroads;


• in an airline graph, a weight may mean the cost of a flight between two cities;


• in a currency exchange graph, a weight may mean the exchange rate between two currencies.

The weight extends naturally to walks, paths, and cycles: the weight of a collection of edges is the sum of the weights of the edges in this collection. For example, the weight of a path \(A \to B \to C \to D\) in the graph above is equal to \(3+4+5=11\). In many applications, we will be interested in finding a path of the minimum weight between two nodes. It is called a shortest path and the minimum weight itself is called the distance.