CODEWITHSUNDEEP
algorithmmathgraph-theorygraph-algorithmshortest-path
GBleaney
GBleaney

Reputation: 2196

How to find the shortest path between nodes?

I am working on a mapping application that finds the shortest route between the things a user wants. Each thing the user wants (such as bread or gas) has multiple possible locations. Currently, I am simply planning the route between the user and the closest instance of each item to the user, however; this is not always the best route. As outlined in the diagram below, the fastest route sometimes involves visiting clusters of further away node: enter image description here For each item, I have up to fifty possible nodes (locations). How can I plan the shortest route that visits every node (in any order)? While pointers to specific examples of how to solve this would be great, all I'm really looking for is a point in the right direction to begin solving this problem.

Upvotes: 4

Views: 1526

Answers (3)

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

You might want to check out chapter 3 of this dissertation for an overview of techniques for solving the vehicle routing problem.

To start out, I would assign a weight to each node based on its distance to the next nearest resource nodes, for example a Gas node that's distance 5 from a Bread node and distance 8 from a Walmart node would have a weight of 13; now go to the Gas node with the lowest weight + distance-from-current-position.

The problem with this heuristic is that it doesn't take into account the distance between the Bread and Walmart nodes - they could be right next to each other, or they could be up to distance 13 from each other. An alternate heuristic is to find the centroid of the subgraph formed by the Gas-Bread-Walmart triangle (or square or pentagon etc depending on how many types of locations you need to visit), add up the distances from the centroid to the points in the subgraph, and use that as the vertex weight.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Small number of items

If your number of items is small you can solve it by using Djikstra on a new graph.

Make a node for each combination of location and which items you have collected.

Use Djikstra to find the shortest route from your start to any node with all items collected.

For L locations and N items, there would be L*2^(N-1) of these new nodes so this is only practical for small N.

Large number of items

I found that ant colony optimisation gave very good results for a similar problem I looked at recently, so this may also be worth a look.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363567

A solution to this problem can be found by introducing a new graph G':

  • the nodes in G' are simple paths through the original graph
  • an edge exists between two nodes when they correspond to partial paths p and p' s.t. p can be extended into p' by adding a node to it.

In this graph (which is huge, so don't explicitly represent it in memory), your desired tour can be found using something like A* search.

Upvotes: 1

Related Questions