Click this link to download an archive containing the Xcode project with my code for Dijkstra's algorithm. You are going to use this code as the starting point for the assignment.
In this exercise we are going to implement an alternative version of Dijkstra's algorithm. In this version we search for the shortest path between a start vertex s and a destination vertex w by running two copies of Dijkstra's algorithm at the same time. One copy will search outward from s, while the other will search outward from w.
To do this, set up an algorithm that uses two separate priority queues, Q1 and Q2. Also, instead storing a single d and π values in each vertex you will store a d1, π1 pair and a d2, π2 pair in each vertex. My solution does not use an S set, but you will need to keep track of which vertices have been processed by each search.
On each round of your algorithm you will pull one vertex off of Q1 and one vertex off of Q2 for processing. As soon as you detect a vertex m that has been processed by both searches you should stop and print the shortest path from s to m followed by the shortest path from m to w, along with the total length of the path from s to w that you found. Does your algorithm find the same shortest path from s to w that my original algorithm found?