Search code examples
c#algorithmdijkstrapath-finding

Use Dijkstras to find the "k" shortest path

It is already possible for me to find the shortest route between two vertex points, using Dijkstra's algorithm: wiki Dijkstra's.

BUT. Some of my edges are meant to be used as "checkpoints", as in you have to go through at least one checkpoint in order for a route to be available.

Sometimes, the algorithm will find a path that contains none of these edge-checkpoints. In that case I want to find the 2nd. shortest route - and if that route doesn't contain a checkpoint either, then find the 3rd. shortest route, and so on.

Any ideas how to get me started?

EDIT:

Would it be possible to go through all the predecessors on the first route, and then run Dijkstras from the predecessor to the destination (and exclude the original choice of the predecessor's next goto vertex). In that way I could possibly find all possible routes, and then compare them to each other?

Example.

A = source Z = destination

shortest path: A -> B -> C -> D -> Z

2nd. shortest path: A -> B -> C -> D -> "Vertex with lowest cost, which is NOT Z" (loop this through all D's unvisited neighbors if it doesn't find an available path in current try)

if 2nd. shortest path doesn't contain checkpoint either, try 3rd shortest

3rd. shortest path: A -> B -> C -> Vertex with lowest cost, which is NOT D

Or is this solution not possible in any way?

EDIT 2:

Picture It may be very hard to see, but the purple 1x3 pixels are the vertices. The yellow roads are edges, and so are the pink 3x3 pixels. The pink ones are also the so called checkpoints. So I have to find the shortest route and go through at least one checkpoint.

Solution

  • There are a few ways you could attempt to make this work.

    Let's call S the starting node, D the destination node, and I the intermediate node.

    [Single Intermediate node] A simple but sub-optimal solution would be to use Dijkstra from S to I and then append the result of Dijkstra from I to D.

    [Multiple Intermediate nodes] As Niklas B. pointed out a feasible approach would be "Build the shortest path trees from S and D. For each intermediate node A, check d(S, A) + d(T, A). The minimum is the solution. Runtime is twice that of Dijkstra, e.g. O((n+m) log n) with binary heaps".