TransWikia.com

Yen's or Eppstein for path with intermediate destinations which are dangling nodes

Geographic Information Systems Asked by mauegraus on August 9, 2020

I’m trying to find a shortest path algorithm (which does not need to be optimal) for a path with intermediate destinations. Consider the following case: One wants to go from A to Z and in between wants to visit B and C. For both, B and C, there are multilocal options,b1 and b2, and c1 and c2. Just to make it more practical, I want to go from my place (A) to a friends place (Z), but on my way I want to visit a supermarket (B), of which there are two in the area (b1 and b2), and I want to go to a pharmacy, of which there are also two in the area (c1 and c2). The order of whether I first visit the supermarket or the pharmacy does not matter, but I favor the shortest path to my friend. Accordingly, I need the shortest path from A to Z with an (close to) optimal ordering of the intermediate destinations B and C. I hope this is understandable.

Now, I first thought I may first calculate all shortest paths between a certain option of an intermediate destination (let’s consider here b1) and the start node (A), the destination node (Z) and the nodes of the options of the other intermediate destination (c1 and c2). Accordingly I would calcuate a shortest path (e.g. with Dijkstra) between:

b1 – A

b1 – Z

b1 – c1

b1 – c2

The algorithm would do this also for b2, c1, and c2, would order it then and select the shortest path which would include one option of B and one of C. However, with increasing options and as such an increasing network the peformance would be low.
Therefore I thought to use the Yen’s algorithm. This would lengthen the path between A and Z artificially, and I would include an iteration restriction (e.g. after calculating 100 paths, stop), then ordering the paths according to some priority. Accordingly, it should give out one shortest path between A and Z which would include at least one option (node) for B and one for C.
However, here find a challenge to use it for my network. Have a look at the first image. red nodes = end nodes and target nodes
The red nodes are dangling nodes, but these nodes are also options for intermediate destinations. When I understand the Yen’s correctly, dangling edges would cause the algorithm to stop iterating before it achieves the destination, and as such,no path would include intermediate destinations which are within a dangling branch. Instead of stop iterating, the algorithm would need to go the danling branch backwards and iterate further until it reaches node Z. Have a look at the arrows of the second image , which show which path it would need to calculate. arrows showing the path needed to be calulated.
Those ‘dead branches’ need to be gone forwars AND backwards and, in the end, included in the path. Is this named to be a ‘loop’?
I hadn’t had a look at Eppstein yet, but I think it includes the possibility of having also loops in the path. But… is this a loop??
If someone out there has experience with Yen’s or Eppstein I would be glad to hear his/her opinion on this case!
I also thought about merging the information of the nodes within the dead branch to the closest inbound node, or generate a new node on the closest, relevant edge. For example, in the first image, this would result in that the node a would get the information from node b, and the node c would get the information from the nodes d and e. However, I find this semioptimal as in some cases imprecise (example of such a case would be node e, as it is in a little distance from c).

One Answer

I think it needs algorithm that able to cope loop paths. The problem you described is clearly loop paths. Yen algorithm is used for loop less paths. So, one of the possible algorithms to solve it is using Eppstein algorithm.

Answered by user166240 on August 9, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP