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