[Expert Solution]: In an emergency, a building has to be…

In an emergency, a building has to be evacuated in a hurry. When a disaster strikes, an evacuation plan should be in place and there are many aspects that such a plan takes into consideration: https://www.osha.gov/SLTC/etools/ evacuation/evac.html. Let us consider a much simplified version. Let G = (V,E) be a directed graph, representing a building. Every vertex v in V represents a room, and every edge (u, v) in E represents a corridor that leads from room u to room v (there may be also an edge (v,u)). For every corridor (u, v) in E, at most cu,v people can traverse it simultaneously in the direction from u to v, where cu,v is a positive integer. Traversing a corridor takes one time step, and traversing a room takes zero time. Suppose that there are k people in the building, all initially located in some room s in V , and they all want to move to some room t in V (e.g., exit). Give an algorithm that computes the fastest possible way for all people to move from room s to room t. The running time of your algorithm should be polynomial in both n, and k (for example, O(|V |10k10)).