algorithm to find shortest path connecting EVERY node

Question

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?

Steven · Answer

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.

algorithm to find shortest path connecting EVERY node

One Answer

Add your own answers!

Ask a Question