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