In a shortest path problem, when "real travel" through a network can end at more than one node:
I. An arc with length 0 is inserted.
II. The problem cannot be solved.
III. A dummy destination is needed.
A) I only.
B) II only.
C) III only.
D) I and II only.
E) I and III only.

Question

Quizplus · Accepted Answer

When real travel can end at more than one node, a dummy destination is needed to ensure that the problem has a unique solution. However, simply adding a dummy destination may result in some of the actual destinations being bypassed in the shortest path. Therefore, to ensure that all actual destinations are included, an arc with length 0 is inserted between the dummy destination and each actual destination. This guarantees that the shortest path will include all actual destinations and end at the chosen dummy destination. It does not mean that the travel time between the dummy destination and the actual destinations is 0, but rather that the arc between them is simply a placeholder to ensure that all destinations are reached in the shortest path. If no dummy destination is used and there are multiple possible endpoints, the problem cannot be solved because there is no unique shortest path.

In a Shortest Path Problem, When "Real Travel" Through a Network