Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose distance to every other node on the graph is equal to zero. Can I run Dijkstra's algorithm (either alone, or with other DP functions) to return to the shortest path after trying all paths from a location on the graph (the dummy node), with an exit condition that once every node has been visited,return to zero? If the solution is ran with the dummy node as the starting point, the final result must contain the sequence "start - dummy node - end". Wouldn't this lead to the shortest Hamiltonian path?
1 Answer
$\begingroup$
$\endgroup$
2
I could be misunderstanding you, but the answer is no. Dijkstra's requires you to specify the start node and the end node, and returns the shortest path between them.(It can actually tell you the shortest path from the start node to every other node, but that isn't crucial here.) There is no reason that this path would contain all of the nodes of the original graph.
-
$\begingroup$ That makes sense, and aligns with what I understand about Dijkstra's algorithm With that being said, what sort of DP solution might work here? $\endgroup$ Nov 17 at 23:10
-
$\begingroup$ You want to solve the Hamiltonian path problem using Dynamic Programming? A quick Google search returned this: geeksforgeeks.org/hamiltonian-path-using-dynamic-programming Is there a reason you specifically want to use Dynamic Programming? $\endgroup$ Nov 17 at 23:46