Problem 3: Greedy routing. Communication networks (such as the internet) use various algorithms for transmitting information between different nodes. One popular such algorithm is greedy routing, which works as follows. Let G be a directed graph and suppose that each (u, v) E(G) has some non-negative length (u, v), which encodes the delay incurred when transmitting a message from node u to node v. Suppose that we wish to transmit a message from some node s to some node t. If s and t are connected via an edge (that is, if (s, t) E(G)) then we send the message directly to t. Otherwise, we pick the neighbor s' of s that is closest to t, and we transmit the message to s' . This process continues until the message arrives at t.

(a) Suppose that G is strongly connected. Show that the above greedy routing algorithm always successfully delivers the message to the destination t in a finite number of steps.

(b) Recall that the shortest path between two nodes in a graph is a path of minimum length (i.e. sum of the lengths of all the edges in the path). Does the above algorithm always transmit messages along a shortest path from s to t in G? Justify your answer. If your answer is yes, provide a proof. If your answer is no, provide a counterexample