# algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use.

TLDR; Find the shortest path to get to every node in a undirected graph

The problem states that one must visit every station in the shanghai metro in the shortest path possible. Interchange Stations ('edges') can be reused and you can start / stop anywhere.

I have created a lookup table that shows connected stations as well as the distance to travel (not shown)

"Xinzhuang": [
"Waihuan Rd." : 1
],
"Waihuan Rd.": [
"Xinzhuang": 2.2,
"Lianhua Rd.": 3
],
"Lianhua Rd.": [
"Waihuan Rd.": 4,
"Jinjiang Park": 5,
],
"Jinjiang Park": [
"Lianhua Rd.": 9.1,
"South Railway Station": 10.3
],
"South Railway Station": [
"Jinjiang Park": 4.1,
"Caobao Rd.": 1.1,
"Shilong Rd.": 2.5
],
...


I found this leetcode problem but it did not mention any specific algorithm and since it was O(2^N * N) I wondered if there was a faster method than BFS.

https://leetcode.com/problems/shortest-path-visiting-all-nodes/solution/

Since my graph is so big, I was going to reduce the lines with a single path to a single node.

What algorithm can I use that will work in Polynomial time, OR has the least time complexity?

There is no polynomial-time algorithm for your problem unless $$P=NP$$, since it captures the Hamiltonian path problem as a special case.
Moreover, unless the exponential time hypothesis fails, there is no $$2^{o(n)}$$-time algorithm for your problem, where $$n$$ is the number of vertices.
• Yes, the Hamiltonian problem requires the path to visit each vertex exactly once. However your problem is more general (i.e., not easier than) than the Hamiltonian path problem. You can easily reduce an instance of Hamiltonian path to your problem as follows: Given a graph $G$, consider each edge of $G$ as having weight $1$. The length of a shortest path that visits each vertex at least once is $n-1$ $\iff$ there is an Hamiltonian path in $G$. Jul 20 '20 at 23:04