Problem

Given an undirected graph, find the shortest path between two nodes.
Input:
1 2
2 3
3 4
4 5
Output:
1 2 3 4 5

Solution

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct Node {
    int val;
    vector<Node*> neighbors;
    Node(int v) : val(v) {}
};

void printPath(Node* start, Node* end) {
    if (start == end) {
        cout << start->val << " ";
        return;
    }
    printPath(start, end->neighbors[0]);
    cout << end->val << " ";
}

void printShortestPath(Node* start, Node* end) {
    if (start == end) {
        cout << start->val << " ";
        return;
    }
    unordered_map<Node*, Node*> parent;
    unordered_set<Node*> visited;
    queue<Node*> q;
    q.push(start);
    visited.insert(start);
    while (!q.empty()) { Node* cur = q.front();
        q.pop();
        for (Node* neighbor : cur->neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                parent[neighbor] = cur;
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
    printPath(start, end);
}

int main() {
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    n1->neighbors.push_back(n2);
    n2->neighbors.push_back(n1);
    n2->neighbors.push_back(n3);
    n3->neighbors.push_back(n2);
    n3->neighbors.push_back(n4);
    n4->neighbors .push_back(n3);
    n4->neighbors.push_back(n5);
    n5->neighbors.push_back(n4);
    printShortestPath(n1, n5);
    return 0;
}