1. Describe an algorithm for determining a most vital arc in a directed network. What is the running time of your algorithm?
2. A longest path is a directed path from node s to node t with the maximum length. Suggest an O(m) algorithm for determining a longest path in an acyclic network with nonnegative arc lengths. Will your algorithm work if the network contains directed cycles?