Select Git revision
-
Jiahang Chen authoredJiahang Chen authored
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
main.cpp 2.13 KiB
#include <iostream>
#include <unordered_map>
#include <vector>
#include <list>
using namespace std;
class Node;
class Path;
Path *bfs(int start, int end, int max, unordered_map<int, node> nodes);
class Node {
int year;
Path* shortest_path;
};
class Path {
vector<Node* > nodes;
};
int main()
{
cout << "Finding the shortest path from 2018 to 1889 using BFS" << endl;
unordered_map<int, Node> nodes;
Path* result = bfs(2018, 1889, 1000000000, nodes);
for(int i=0; i < result->nodes.size()-1; i++)
{
cout << "Reise von " << result->nodes[i]->year << " nach " << result->nodes[i+1]->year;
}
return 0;
}
Path *bfs(int start, int end, int max, unordered_map<int, node> nodes)
{
//Generate a starting node
Node start_node;
nodes[start] = start_node;
start_node.year = start;
//Generate a path for the starting node
Path start_path;
start_path.nodes.push_back(&start_node);
start_node.shortest_path = &start_path;
list<Node* > queue;
queue.push_back(&start_node);
while (!queue.empty()) {
//Get and check the first element from the queue
Node *current_node = queue.front();
queue.pop_front();
if(current_node->year == end)
{
cout << "Target node found" << endl;
return current_node->shortest_path;
}
int c_year = current_node->year;
//Check the child nodes
{
if(c_year + 7 <= max)
{
if(nodes.find(c_year + 7) == nodes.end())
{
//Generate child node
Node* child = new Node;
//Set correct year
child->year = c_year + 7;
//Copy over path
Path* child_path = new Path;
child_path->nodes = current_node->shortest_path->nodes;
child_path->nodes.push_back(child);
child->shortest_path = child_path;
}
}
}
//Delete this path, as it will not be used anymore
delete current_node->shortest_path;
}
}