0
$\begingroup$

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks.

Somebody online asked (but nobody answered) how one would go about modifying Dijkstra's algorithm to determine if an electric car can travel to every town in a weighted, undirected graph with a limited number of recharges.

I was curious if anybody had any insight about this.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Wanting to travel to every town transforms this problem into a Traveling salesman problem, and Dijkstra cannot be of any (known) help for that.

There is an easy reduction from TSP to your problem: consider that there is a recharge station only in the first town, and ask if it is possible to do a tour with only your battery.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That is a very interesting reply, thank you! From my understanding, the traveling salesman problem requires that the salesman return to the city of origin, which is not necessarily specified in this problem. So my follow up question is; can a generalization of the traveling salesman problem not require that the "salesman" return to the "city" of origin? I know that the Hamiltonian path problem can specify a beginning and ending point, but I am unsure if the Hamiltonian path problem is a generalization of the TSP. $\endgroup$
    – Johnny Upman
    Nov 17 at 1:04
  • $\begingroup$ I am also unsure if the electric car problem can be generalized as a Hamiltonian path problem.. $\endgroup$
    – Johnny Upman
    Nov 17 at 1:16
  • $\begingroup$ It is not necessary to go back to the origin for the problem to be $\mathsf{NP}$-complete. $\endgroup$
    – Nathaniel
    Nov 17 at 6:01
  • $\begingroup$ My conclusion as well. The car problem is not a TSP, but a Hamiltonian path problem, which is still NP-complete. Thanks for setting me on the right path. $\endgroup$
    – Johnny Upman
    Nov 17 at 9:49
  • $\begingroup$ Hamiltonian problems concern non-weighted graphs, that's why I am talking about TSP. $\endgroup$
    – Nathaniel
    Nov 17 at 12:36

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.