Search code examples
graphdijkstrapath-finding

What pathfinding algorithm should I use for this?

I have a graph (city map) with set of nodes I need to visit. And I need to create an optimal route, so I used dijkstra's algorithm. The problem is that this algorithm is for finding optimal route from one node to any other which is not enough for me because I have discrepancies along the way. For example: enter image description here

The red route is the path I get from Dijkstra's algorithm (from a to c node), but I don't know what I should do if I want to visit node b too. So, is there any algorithm that would fit my case?

Solution

  • Dijkstra's finds the shortest (or least expensive) path between two given nodes. If you want to visit a larger set of nodes, you are looking at the Travelling Salesman Problem.

    In the classic TSP, you must visit all nodes in the graph. I don't know if your subset problem has a name, but you can use Dijkstra to find the shortest path between every pair of cities to be visited, reducing your visit-three-cities-out-of-nine to the simpler visit-three-cities which TSP deals with.

    A brute-force solution to TSP is O(n!), which is not too bad for a small number of nodes to be visited. Faster algorithms exist, but they are much more advanced, and they aren't exactly fast (O(n22n)). Finding a polynomial-time algorithm would get your name in the history books.