4. Suppose that you have a weighted, undirected graph, and are trying to find the length of the shortest path from a node s to some other node t. You decide to use Dijkstra's algorithm for this. However, your graph is gigantic, and running Dijkstra's on the whole thing will take a very long time. So instead, you perform two simultaneous searches in parallel. In one search, you begin at node s, and gradually discover shortest paths from s to other nodes. In the other search, you begin at node t, and gradually discover shortest paths from t to other nodes (and because the graph is undirected, this process also tells you the shortest paths from those nodes to t). In each iteration, suppose the first search has discovered shortest paths from s to some set of nodes Rs, and the second search has discovered paths from t to some set of nodes Ri. Initially, Rs only contains s and Rt only contains t. This process continues until Rs and Rt have some overlap; that is, you find some node u that is present in both Rs and Rt. Then if the distance from s to u is di and the dis- tance from u to t is d2, you report that the distance between s and t is di+d2 Will this procedure give you the correct shortest path from s to t? If yes, prove that it will work. If no, give an example showing where it can fail