3. (5 points) Bellman-Ford algorithm for finding shortest paths. In class, we discussed the following variant of the Bellman-Ford algorithm, whose pseudocode is below. While true f For all edges e = u--> v { dist [v] min(distIv], dist[u]1(u >v)); if no vertex's dist value is changed, stop 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 algorithm actually needs to run. For such a discussion, it is important to fix an ordering by which we consider the edges, that is we view the edges as a fixed list, e...e (a) (1 point) For any n, exhibit a graph and an ordering of the edges where the Bellman-Ford algorithm takes more than n/2 steps. (b) (2 points) Show that for any graph G without negative cycles and any s-t pair, there exists an ordering of edges so that dist ul (as defined in the pseudocode above) becomes the value of the true s to t distance in 1 step. (c) (2 points) Consider the k k square grid with two-way edges of positive length, 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, (n, c) (r2, c), and we can produce edge ordering by sorting lexicographically via these tuples. For example, on a 2 x 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)