You are given a directed graph G = (V, E), where each edge e has an associated weight 0 < we < 1. You may assume that there is at least one path from every vertex u to every other vertex v, i.e. G has only one strongly connected component. Define the safety of a path consisting of edges e,e2, ..., e as we Your task is to find for each ordered pair of vertices (u, v) the maximum safety of a path from u to v. Design a dynamic programming algorithm which solves this problem and runs in O(n) time.