[C++] write a c++ program that reads a list of cities and the distances between
ID: 3712715 • Letter: #
Question
[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)Explanation / Answer
#include <unordered_map>
#include <vector>
#include <cctype>
#include <limits>
#include <algorithm>
#include <iostream>
using namespace std;
class Graph
{
unordered_map<char, const unordered_map<char, int>> vertices;
public:
void add_vertex(char name, const unordered_map<char, int>& edges)
{
vertices.insert(unordered_map<char, const unordered_map<char, int>>::value_type(name, edges));
}
vector<char> shortest_path(char start, char finish)
{
unordered_map<char, int> distances;
unordered_map<char, char> previous;
vector<char> nodes;
vector<char> path;
auto comparator = [&] (char left, char right) { return distances[left] > distances[right]; };
for (auto& vertex : vertices)
{
if (vertex.first == start)
{
distances[vertex.first] = 0;
}
else
{
distances[vertex.first] = numeric_limits<int>::max();
}
nodes.push_back(vertex.first);
push_heap(begin(nodes), end(nodes), comparator);
}
while (!nodes.empty())
{
pop_heap(begin(nodes), end(nodes), comparator);
char smallest = nodes.back();
nodes.pop_back();
if (smallest == finish)
{
while (previous.find(smallest) != end(previous))
{
path.push_back(smallest);
smallest = previous[smallest];
}
break;
}
if (distances[smallest] == numeric_limits<int>::max())
{
break;
}
for (auto& neighbor : vertices[smallest])
{
int alt = distances[smallest] + neighbor.second;
if (alt < distances[neighbor.first])
{
distances[neighbor.first] = alt;
previous[neighbor.first] = smallest;
make_heap(begin(nodes), end(nodes), comparator);
}
}
}
return path;
}
};
int main()
{
Graph g;
int n;
cout << "Enter number of cities: ";
cin >> n;
unordered_map<char, const unordered_map<char, int>> vertices;
unordered_map<char, int> edges;
int distance;
vector<char> cities;
for(int i = 0; i < n; i++) {
cities.push_back(i+65);
}
for(int i = 0; i < n; i++) {
cities.erase(cities.begin()+i);
cout << "Enter distances for city " << char(i+65) << endl;
for(int j = 0; j < n-1; j++) {
cout << char(i+65) << " -> " << cities[j] << " : ";
cin >> distance;
edges.insert(unordered_map<char, int>::value_type(cities[j], distance));
}
g.add_vertex((char)i+65, edges);
cities.insert(cities.begin()+i, (char)i+65);
edges.clear();
}
cout << "Enter the two cities to find shortest path between them: ";
char src, dest;
cin >> src >> dest;
src = toupper(src);
dest = toupper(dest);
for (char vertex : g.shortest_path(src, dest)) {
cout << vertex << endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.