0
$\begingroup$

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

enter image description here

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ A hamiltonian path visits each vertex exactly once (?), my problem allows for as many times as possible. Does that make a difference? $\endgroup$
    – Peter S
    Jul 20, 2020 at 22:50
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Jul 20, 2020 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.