#### Shortest Path in Undirected Graph

The shortest path between two nodes in an undirected graph can be found by traversing the graph from one node to the other.

#### 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

This solution is in C++. Our A.I. can create solutions in multiple languages.
by kayakane
```#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;
}```

A.I. Evaluation of the Solution

The candidate's solution is complete and solves the problem. The candidate uses a breadth-first search approach to find the shortest path between two nodes.

Evaluated at: 2022-11-29 18:15:51