3.Bellman-Ford algorithm for finding shortest paths. In class, we discussed the following variant of the Bellman-Ford algorithm, whose pseudocode is below. While truet e(dist(v>, dist(u) + 1(u--> v)); distlv] min(dist[v], distlul1(u --v)); if no vertex's dist value is changed, stop eade Please explatn eacn The text book's version (in Section 4.6.) instead fixes the iteration count at e(n). We also showed in class that if we do indeed get to such an iteration count, there must be a negative cycle. In this question, we will discuss how many times the outer loop of Bellman-Ford algorithnm actually needs to run. For such a discussion, it is important to fix an ordering by which we For any n, exhibit a graph and an ordering of the edges where the Bellman-Ford Show that for any graph G without negative cycles and any s-t pair, there exists consider the edges, that is we view the edges as a fixed list, e...em- algorithm takes more than n/2 steps. an ordering of edges so that distlul] (as defined in the pseudocode above) becomes the value of the true s to t distance in 1 step. Consider the k k square grid with two-way edges of positive lengths, we can label each vertex by its row/column number, with the top left corner being (1,1), which is also our source vertex. Then each edge is a 4 tuple, (?, c) ? (T29), and we can produce edge ordering by sorting lexicographically via these tuples. For example, on a 2 2 grid, this would order the edges as: Show that for any k, there exists a set of positive weights for these edges of the k x k square grid so that the Bellman-Ford algorithm with (1, 1) as the starting point takes at least k/10 iterations (the 10 was chosen as an attempt to remove the need of getting constructions with good constants)