Weighted Graphs and Adjacency

A graph $G=(V,E)$ is a pair where $V$ is a set of vertices (or nodes) and $E$ is a set of edges, each connecting two vertices.

In a weighted graph, every edge $e$ carries a real number $w(e)$ called its weight. We write $w(u,v)$ for the weight of the edge between vertices $u$ and $v$. If there is no edge between $u$ and $v$, then $w(u,v)$ is undefined.

In airline routing, vertices represent airports and edges represent nonstop flights. The weight $w(u,v)$ typically encodes the distance in miles, the flight time, or the ticket cost.

For example, consider a network on $\{A,B,C,D\}$ with flights

• $A\text{--}B$ with weight $300$
• $A\text{--}C$ with weight $500$
• $B\text{--}D$ with weight $450$
• $C\text{--}D$ with weight $200$

Then $w(A,B)=300$ and $w(C,D)=200$.

The total weight of a multi-edge route is the sum of the weights of its edges. For instance, the trip $A\to B\to D$ has total weight

$$w(A,B)+w(B,D)=300+450=750.$$