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