Section 7.3 Weighted Graphs
We now pivot to weighted networks and consider some natural optimization problems to pose about them.
Exploration 7.3.1.
Dr. Ayad is driving from her home to Fantasi College. The town is connected by a series of one way streets, each labeled with the time it would take to traverse the road.
(a)
What is the shortest amount of time needed for her to arrive at Fantasi College?
(b)
Is there a unique route she could take that minimizes this time?
Definition 7.3.2.
A network is weighted if for each edge \((v_i, v_j)\in E\) we assign (potentially negative!) weight \(w_{ij}\text{.}\)
Definition 7.3.3.
Give a network \(N\text{,}\) a path \(P\) from \(v_x\text{,}\) \(v_y\) is a sequence of consecutive edges \((v_{a_0}, v_{a_1}), \ldots (v_{a_i}, v_{a_{i+1}}),\ldots, (v_{a_{k-1}}, v_{a_k})\) where \(v_{a_0}=v_x, v_{a_k}=v_y\text{.}\) We say that the length of \(P\) is \(\displaystyle \sum_{i=0}^{k-1}w_{a_ia_{i+1}}\text{.}\) We say that the distance from \(v_x\) to \(v_y\text{,}\) \(d(v_x, v_y)\text{,}\) is the length of a shortest path from \(v_x\) to \(v_y\text{.}\)
Activity 7.3.4.
Consider the weighted network:
(a)
What is the shortest path from \(v_0\) to \(v_4\text{?}\) (You may repeat edges.)
(b)
What if we change \(w_{23}=-1\text{?}\)
(c)
What is a reasonable condition for the shortest path to be well defined?
Definition 7.3.5.
We define a cycle in a weighted network to be a path from a vertex \(v_x\) to itself. If the length of a cycle is negative, we call it a negative cycle.
Activity 7.3.6.
In this activity, we model the shortest path problem as a linear optimization problem. Assume \(N\) is a weighted network with no negative cycles. Let \(0\leq x_{ij}\leq 1\) where \(x_{ij}=1\) if \((v_i, v_j)\) is in a shortest path \(P\) from \(v_s\) to \(v_d\text{.}\)
(a)
What is the objective problem?
Maximize \(\displaystyle \sum_i w_{it}x_{it} \text{.}\)
Maximize \(\displaystyle \sum_j w_{sj}x_{sj} \text{.}\)
Maximize \(\displaystyle \sum_{i,j} w_{ij}x_{ij} \text{.}\)
Minimize \(\displaystyle \sum_i w_{it}x_{it} \text{.}\)
Minimize \(\displaystyle \sum_j w_{sj}x_{sj} \text{.}\)
Minimize \(\displaystyle \sum_{i,j} w_{ij}x_{ij} \text{.}\)
(b)
What inequality ensures that exactly one edge of the chosen edges is incident to \(v_d\text{?}\)
\(\displaystyle \sum_i x_{id} \leq 1\text{.}\)
\(\displaystyle \sum_i x_{id} \geq 1\text{.}\)
\(\displaystyle \sum_i x_{id} = 1\text{.}\)
\(\displaystyle \sum_i x_{id} \leq 0\text{.}\)
\(\displaystyle \sum_i x_{id} \geq 0\text{.}\)
\(\displaystyle \sum_i x_{id} = 0\text{.}\)
(c)
What inequality ensures that the chosen edges form a path?
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}=1\text{.}\)
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}\leq 1\text{.}\)
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}\geq 1\text{.}\)
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}=0\text{.}\)
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}\leq 0\text{.}\)
For each vertex \(v_i\neq v_s, v_d\text{,}\) \(\displaystyle \sum_{j} x_{ji} - \sum_{j} x_{ij}\geq 0\text{.}\)
(d)
Why do we not need a constraint for \(v_s\text{?}\)
(e)
Model the shortest path problem in
Exploration 7.3.1 as a linear optimization problem and solve it:
As was the case in previous examples, we introduce a less cumbersome method for finding these shortest paths.
Definition 7.3.7. Dijkstra’s Shortest Path Algorithm.
Let \(N\) be a weighted network with only non-negative weights. Then Dijkstra’s Shortest Path Algorithm is as follows:
INITIALIZE: Let \(R=\{v_s\}\) and let \(T=V\backslash R\text{.}\) Label \(\ell_s=0\text{,}\) \(\ell_i = w_{si}\) if \(w_{si}\) exists, \(\infty\) otherwise.
Let \(v_k\) be a vertex where \(\ell_k=\displaystyle \min_{i\in T} \ell_i\text{.}\)
Let \(R=R\cup \{v_k\}, T=V\backslash R\text{.}\)
If \(T=\emptyset\text{:}\) STOP.
For each \(v_j\in T\text{,}\) let \(\ell_j=\min\{\ell_j, \ell_j+w_{kj}\}\text{.}\)
GOTO 2.
When the algorithm terminates, \(\ell_j = d(v_s, v_j)\text{,}\) the length of the shortest path from \(v_s\) to \(v_j\text{.}\)
Activity 7.3.8.
(a)
Apply
Definition 7.3.7 to the network in this problem and label each vertex
\(v_i\) by
\(\ell_i\text{.}\)
(b)
What do each \(\ell_i\) represent in terms of travel time?
(c)
Consider \(\ell_3, \ell_4\) and \(w_{35}, w_{45}\text{.}\) Which vertex could be on a shortest path from \(v_0\) to \(v_5\text{?}\)
(d)
Take your previous choice of vertex \(v_k\) and repeat: look at the \(\ell_i\) of it’s potential predecessors and \(w_{ik}\text{.}\) Recursively repeat until we reach \(v_0\text{.}\)
(e)
What is the shortest path from \(v_0\) to \(v_5\text{?}\)
Activity 7.3.9.
We prove that in
Definition 7.3.7,
\(\ell_i=d(v_s, v_i)\) for each
\(v_i\in R\) via induction on
\(|R|\text{.}\)
(a)
Verify that the statement is true when \(|R|=1\text{.}\)
(b)
Prove that in step 3, if we select \(v_k\) then \(v_k\) is adjacent to a vertex in \(v_{k}'\in R\text{.}\)
(c)
Let \(|R|=m\geq 1\) and consider \(v_k, \ell_k\) as chosen in step 3. Show that \(\ell_k\) is the shortest distance from \(v_s\) to \(v_k\) traversing only vertices in \(R\cup \{v_k\}\text{.}\)
(d)
Suppose (by way of contradiction) that there was a shortest path \(P\) from \(v_s\) to \(v_k\) where the length of \(P\lt \ell_k\text{.}\) Show that there must be an edge in \(P\text{,}\) \((v_x,v_y\)) so that \(v_x\in R, v_y\not \in R, v_y\neq v_k\text{.}\)
(e)
Show that in this case that \(\ell_x+w_{xy}\leq \ell_k\text{.}\) (Invoke the induction hypothesis).
(f)
Show that the last statement produces a contradiction (why wasn’t \(y\) already chosen?)
(g)
Conclude that \(d(v_s, v_k)=\ell_k\text{.}\)
We present an alternative algorithm for when weights can be negative.
Definition 7.3.10. Shortest Path Algorithm.
Let \(N\) be a weighted network with no negative cycles. Then an algorithm to find shortest paths is as follows:
INITIALIZE: Let \(R=\{v_s\}\) and let \(T=V\backslash R\text{.}\) Label \(\ell_s=0\text{,}\) \(\ell_i = w_{si}\) if \(w_{si}\) exists, \(\infty\) otherwise.
Let \(v_k\) be a vertex where \(\ell_k=\displaystyle \min_{i\in T} \ell_i\text{.}\)
Let \(R=R\cup \{v_k\}, T=V\backslash R\text{.}\)
If \(T=\emptyset\text{:}\) STOP.
For each \(v_j\in V\text{,}\) let \(\ell_j=\min\{\ell_j, \ell_j+w_{kj}\}\text{,}\) if \(v_j\in R\) has a value changed by this process, remove \(v_j\) from \(R\) and add it to \(T\text{.}\)
GOTO 2.
When the algorithm terminates, \(\ell_j = d(v_s, v_j)\text{,}\) the length of the shortest path from \(v_s\) to \(v_j\text{.}\)
Exploration 7.3.11.
Suppose a shipping company is moving goods through a series of transportation hubs via rail. The maximum capcity in tons and the cost in thousands of dollars per ton are listed as an ordered pair:
The pairs are (capacity, cost) pairs (denoted
\((c_{ij}, w_{ij})\)), and we are trying to ship 10 tons of goods from
\(v_0\) to
\(v_5\text{.}\)
(a)
Let’s find a single path from \(v_0\) to \(v_5\) along which we could ship goods at the lowest possible cost. What criteria should we use to identitfy this path?
Maximize \(\displaystyle w_{ij}\) along this path.
Minimize \(\displaystyle w_{ij}\) along this path.
Maximize \(\displaystyle c_{ij}\) along this path.
Minimize \(\displaystyle c_{ij}\) along this path.
(b)
Find a shortest path from \(v_0\) to \(v_5\text{.}\)
(c)
(d)
Decrease capacities of any used edges by \(x_{ij}\text{.}\)
(e)
Repeat (a)-(c) until we have a flow of 10.
(f)
Argue that this is not the lowest cost flow.
(g)
Which of the following was an issue with how this problem was approached?
The original path chosen was too expensive.
The original path forced us into poor choices of future paths.
There was no mechanism to backtrack or adjust previous choices.
Activity 7.3.12.
We model the shipping problem in
Exploration 7.3.11 as a linear optimization problem. Let
\(x_{ij}\) denote the quantity in tons of goods shipped from
\(v_i\) to
\(v_j\text{.}\)
(a)
What is the objective function of this problem?
\(f(\x)=\displaystyle \sum_{i, j}x_{ij}\text{.}\)
\(f(\x)=\displaystyle \sum_{i, j}x_{ij}c_{ij}\text{.}\)
\(f(\x)=\displaystyle \sum_{i, j}x_{ij}w_{ij}\text{.}\)
\(f(\x)=\displaystyle \sum_{j}x_{0j}\text{.}\)
\(f(\x)=\displaystyle \sum_{j}x_{0j}c_{0j}\text{.}\)
\(f(\x)=\displaystyle \sum_{j}x_{0j}w_{0j}\text{.}\)
(b)
For each \(ij\) edge, there is a constraint for the shipping capacity of that edge. What (in)equality represents that capacity?
\(x_{ij}\leq w_{ij}\text{.}\)
\(x_{ij}\geq w_{ij}\text{.}\)
\(x_{ij}= w_{ij}\text{.}\)
\(x_{ij}\leq c_{ij}\text{.}\)
\(x_{ij}\geq c_{ij}\text{.}\)
\(x_{ij}= c_{ij}\text{.}\)
(c)
For each vertex \(v_k\) excluding the source and sink, what (in)equality represents the conservation of flow?
\(\displaystyle \sum_{i}x_{ik}-\sum_{j}x_{kj}\leq 0\text{.}\)
\(\displaystyle \sum_{i}x_{ik}-\sum_{j}x_{kj}\geq 0\text{.}\)
\(\displaystyle \sum_{i}x_{ik}-\sum_{j}x_{kj} = 0\text{.}\)
(d)
Let \(F\) be the total amount of goods to be shipped, in this case \(F=10\text{.}\) What equality represents this constraint?
\(\displaystyle \sum_{i, j}x_{ij}c_{ij}= F\text{.}\)
\(\displaystyle \sum_{i, j}x_{ij}w_{ij}= F\text{.}\)
\(\displaystyle \sum_{i, j}x_{ij}=F\text{.}\)
\(\displaystyle \sum_{j}x_{0j}= F\text{.}\)
\(\displaystyle \sum_{j}x_{0j}c_{0j}=10\text{.}\)
\(\displaystyle \sum_{j}x_{0j}w_{0j}=10\text{.}\)
(e)
Activity 7.3.13.
We return to
Exploration 7.3.11 with an adjustment to the procedure there to enable adjusting previously chosen paths.
(a)
Once again, find the shortest path from
\(v_0\) to
\(v_5\text{,}\) and use this as an
\(\alpha\)-path as in
Definition 7.2.10.
(b)
Now in addition to decreasing the capacities of used edges by \(x_{ij}\text{,}\) add a backwards edge \((v_j,v_i)\) with capacity \(x_{ij}\) and negative weight \(-w_{ij}\text{.}\)
Pick any path from \(v_0\) to \(v_5\) that traverses a backwards negative edge. What does shipping along this path represent in terms of determining a new shipping procedure.
Test your ideas out on a few different paths traversing negative edges.
(c)
Find the shortest path along this adjusted graph and treat it as an \(\alpha\)-path.
(d)
What does this second chosen shortest path represent in terms of shipping goods?
(e)
Have you now achieved a minimal cost flow shipping 10 tons of goods?
We now formalize this idea of adjusting previous choices to an algorithm:
Definition 7.3.14. Minimum Cost Flow Algorithm.
The steps for the Minimum Cost Flow Algorithm are as follows:
INITIALIZE: Let \(N=(V, E)\) be a weighted capacitated network with a unique source \(v_s\) and sink \(v_d\text{,}\) with no edges going into the source and no edges coming out of the sink. We start with the zero flow \(x_{ij}=0\) for each edge \((v_i, v_j)\text{.}\) Let \(F\) be the desired total flow.
If \(\displaystyle \varphi(v_d)=\sum_{i} x_{id}=F\text{,}\) STOP, we have reached a total flow of \(F\text{.}\)
Form a weighted network \(N'=(V', E')\) as follows:
Let \(V'=V\)
Let \((v_i, v_j)\in E'\) if and only if \(x_{ij}\lt c_{ij}\text{.}\) Let \(w'_{ij}=w_{ij}\text{.}\)
Let \((v_j, v_i)\in E'\) if and only if \(x_{ij} > 0\text{.}\) Let \(w'_{ij}=-w_{ij}\text{.}\)
Apply Dijkstra’s Shortest Path Algorithm on \(N'\) to find the shortest path from \(v_s\) to \(v_d\text{.}\) If no path exists STOP, there is no flow with total value \(F\text{.}\)
Find the \(\alpha\)-path corresponding to the shortest path found in (4). Let
\begin{equation*}
q = \displaystyle \min_{(v_i, v_j) \in \alpha}\left\{ \min_{(v_i, v_j)\text{ forward }}\{c_{ij}-x_{ij}\}, \min_{(v_i, v_j)\text{ backwards }}\{F-\varphi(v_d) \}\right\}
\end{equation*}
Add \(q\) to each forward \(x_{ij}\) in \(\alpha\text{,}\) and subtract \(q\) from each backwards \(x_{ij}\) in \(\alpha\text{.}\)
GOTO 2.
