[C++]

write a c++ program that reads a list of cities and the distances between them (distances will be integers). Asks the user to enter two city names and finds the shortest path length.

"Let the node at which we are starting be called the initial node. Let the distance of node Ybe the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step. 1. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set. 2. Assign to every node a tentative distance value: set it to 0 for our initial node and to infinity for all other nodes. Set the initial node as current, 3. For the current node, consider a of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B through A will be 6+ 2-8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. 4. When we are done considering all of the neighbors of the current node, mark the current node 5. Move to the next unvisited node with the smallest tentative distances and repeat the above 6. If the destination node has the smallest tentative distance among all "unvisited" nodes, then 7. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as visited and remove it from the unvisited set. A visited node will never be checked again. steps (3 and 4) which check neighbors and mark visited. stop. The algorithm has finished. as the new "current node", and go back to step 3." Here is a pseudo code for this algorithm that finds the shortest path length between source and destination: For each vertex v in graph: Set dist[v] to infinity Set dist[source] 0 Add all vertices to U curremove from U vertex with smallest tentative distance (source) while cur is not destination: for each neighbor v of cur: if dist[cur] edge_between (cur, v)