P$2$

Consider the digraph below

Assuming that the labels on the arcs represent traveling costs, find a $1-8-$path of minimum cost using

Dijkstra's method

Assuming that the labels on the arcs now represent arc capacities, find a maximum flow using the aug$-$

menting path algorithm. Initialize the algorithm with the solution where $0$ flow is sent on every arc.

Identify a $1-8-$cut of minimum capacity

Assuming that the labels on the arcs now represent weights and that the arcs are undirected, find a

minimum spanning tree using Prim's method