All shortest paths in a graph using K reverse edges

Question

Let's say i have a directed graph G(V,E) with positive integer weights at it's edges.What i need to do is find the shortest paths between all vertices using at most K(integer) reverse edges.What i mean by that is:If we are at edge u and there is only a directed edge from v to u we can use it as long as we have not used K reverse edges for this path.This has to be implemented in C++ and give the shortest paths as a result.

I thought about running dijkstra V times(something like Johnson's algorithm)but i am not sure how to take advantage of the reverse edge property.Any ideas?

Answer 1

The common approach to problems like this is usually described as "layering". You (conceptually) make K+1 copies of the graph, G₀ to G_K, and then connect a vertex u_i in G_i to a vertex v_i+1 in G_i+1 if there is an edge from v to u in G.

A path from s₀ in G₀ to t_i in G_i then represents a path from s to t in G that uses i reverse edges, where i is at most K.

You can just use Dijkstra's algorithm on this new layered graph.

When you get used to this you can think about it in an even simpler way: you just use Dijkstra's algorithm, but instead of having states in the queue like [reached v, with cost c], you use states like [reached v, with cost c, having used i reverse edges]. Often, when we use Dijkstra's in real life, there is no actual graph given, so it helps to think of it as a search through states and their transitions.