2
$\begingroup$

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm?

You can visit those way stations in any order. There will be multiple origins and multiple destinations, but a path from any origin to any destination will suffice as long as it's the shortest.

$\endgroup$
  • $\begingroup$ There are two orthogonal concerns here. Can you figure out how to manipulate the graph for multi-source multi-destination without waypoints? How about the other way round? $\endgroup$ – Peter Taylor May 29 at 6:37
  • $\begingroup$ @PeterTaylor Without waypoints, it seems fine to use Dijkstra, I initialize the distance for all the source nodes to be 0, and the remaining nodes infinity. Then run the dijkstra on it with a priority queue, whenever I hit one of the destinations, the algorithms stops. Does that sound right? But once I introduce the waypoints, then it doesn't work... $\endgroup$ – Dijkstra's admirer May 29 at 7:25
0
$\begingroup$

Unless I'm misunderstanding the problem, you can't solve this with any simple modification to Dijkstra's because it's NP-complete.

Given an arbitrary graph, call every node a "waystation", then add start/finish nodes that are fully connected. Now running the solver for your problem will solve TSP on the original graph.

$\endgroup$
  • $\begingroup$ Nothing in the question says anything about polynomial running time. $\endgroup$ – Peter Taylor May 29 at 7:31
0
$\begingroup$

You're most of the way there in the comment with the handling of multiple sources and destinations. The simple way to do it is to insert two new vertices: the new source, with a 0-weight edge to each of the multi-sources, and the new destination, with a 0-weight edge from each of the multi-destinations.


For the waypoints, I will quote myself:

This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.

Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of ...

here, the knowledge of which waypoints you've already visited. So $G'$ is potentially considerably larger than $G$.

Hint:

If there are $k$ waypoints, $G'$ will contain $2^k$ copies of $G$, plus some edges connecting them.

$\endgroup$
0
$\begingroup$

You should build a distance matrix with:

  • one row respresenting any origin and $k$ rows for the $k$ waypoints
  • one column representing any destination and $k$ columns for the $k$ waypoints.

To fill this matrix, you can run $k+1$ Dijkstra algorithms for each row (time complexity $O(k(|V| + |N|\log |N|))$). For the row any origin, you just start with all origins at distance 0 in your heap.

Then you come to the NP-complete part, you indeed have to solve Travelling salesman problem on your distance matrix, starting on the any origin row and finishing on the any destination column. There are many ways to process it but for small $k$, you can simply use brute force (time complexity $O(!k)$).

So you obtain the shortest distance of the path answering to your problem and the ordered sequence of the waypoints visits. To obtain the path you can run again $k+1$ Dijkstra algorithms to build the path waypoint by waypoint. You can either have stored the path of any value of the distance matrix building it (space complexity $O(|N|k^2)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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