Final answer:
To prove that the galactic shortest-path problem is NP-complete, one method that can be used is a reduction from a known NP-complete problem, such as the Hamiltonian path problem. By performing this reduction, one can show that if there exists a polynomial-time algorithm for the galactic shortest-path problem, then there also exists a polynomial-time algorithm for the Hamiltonian path problem.
Step-by-step explanation:
To prove the galactic shortest-path problem is NP-complete, a reduction from a known NP-complete problem can be used. In this case, the reduction can be from the Hamiltonian path problem, which is a well-known NP-complete problem. The reduction can be done by constructing an instance of the Hamiltonian path problem using the galactic shortest-path problem.
First, we need to define the Hamiltonian path problem: given an undirected graph, does there exist a path that visits every vertex exactly once? To reduce this problem to the galactic shortest-path problem, we can assign a weight of 1 to each edge of the graph, making the galactic shortest-path problem equivalent to finding the shortest path that visits every vertex exactly once.
By performing this reduction, we can show that if there exists a polynomial-time algorithm for the galactic shortest-path problem, then there also exists a polynomial-time algorithm for the Hamiltonian path problem, which is an NP-complete problem. Therefore, we can conclude that the galactic shortest-path problem is also NP-complete.