Graph with colored edges: shortest paths with at most k color changes?

Question

I have a directed graph with coloured, weighted edges. There are 2 colours. Each edge can have only 1 colour. I want to find shortest path with limited changes of colours. From one vertex there can be max 2 edges with 2 different colors going out and 2 edges with 2 different colors going in.

For example in this graph:

Shortest path with maximum of 3 colour changes will be 9 With max 0 colour changes shortest path is 6+1+4=11, etc.

My solution is to recursively visit all possible paths and exchange if recursion find a better one which makes this problem exponential.

Is there a non-exponential solution to this problem?

Answer 1

This can be solved in time O(nm + n² log n) by running Dijkstra's algorithm on an appropriately-constructed graph.

To motivate the intuition for where we're going, let's assume for now that the optimal path makes at most one color change and starts by following a red edge. The path therefore either follows no blue edges, in which case we only follow red edges, or it follows some number of red edges, then some number of blue edges.

Think about what happens if you transform G as follows:

• Begin by copying the nodes in the graph twice to give two layers G0 and G1. We'll denote the copy of node v in G0 as v0 and the copy of node v in G1 as v1.
• For each blue edge (u0, v0), replace that edge with the edge (u0, v1).
• Delete all red edges from G1.

You can think of this graph as two copies of G stacked on top of one another with some tweaks to the edges. Specifically, edges running inside of G0 are all red, and the blue edges take you down to G1. There are then no red edges in G1.

Think about what a path in this graph looks like. If you stay purely in G0, it consists only of red edges. If you start in G0 and end up in G1, then the path starts of by following some number of red edges, then at least one blue edge, and then some larger number of blue edges. Therefore, any path in this graph will have exactly one color change involved.

You can use this graph to find the shortest path from a node u to a node v that makes at most one color change. Start by running Dijkstra's algorithm starting at u, and look at the distances of v0 and v1. The distance to v0 is the length of the shortest path to v0 that makes no color changes. The distance to v1 is the length of the shortest path to v1 that makes at most one color change. The shorter of these two distances then gives you the length of the shortest path from u to v that makes at most one color change.

We can extend this trick to work for any number of steps k as follows. Create k copies of G, called G0, G1, G2, ..., G(k-1). Assuming the path starts with a red edge, we can then change the graph as follows. Make all blue edges in G0 instead run from G0 to G1. Then, make all red edges in G1 run from G1 to G2. Then, make all blue edges in G2 run from G2 to G3, etc. Finally, delete all edges out of G(k-1) that are not of the color leading into G(k-1). This graph maintains the same property as before - any path from a node u0 to a node v_r represents a path from u to v that makes exactly r color changes, assuming the first edge is red. The best path making at most r color changes can then be found by looking at the lowest cost of the paths to v_0, v_1, ..., v_(k-1).

This approach so far assumes that the first step is red, but we're not guaranteed that's the case. But that's okay - we can run this algorithm once assuming the first step is red and once assuming the first step is blue and take the best of both options.

So how expensive is this? Well, if we get at most k color changes, the graph we construct will have a total of O(nk) nodes and O(mk) edges, so constructing it will take time O(k(m + n)). Running Dijkstra's in the graph to find the shortest paths to all the destination nodes then takes time O(mk + nk log nk), so the total runtime is O(mk + nk log nk).

We can actually upper-bound this at O(mn + n² log n) for the following reason: since all edges have strictly positive weight, we know that no path can make more than n - 1 color changes. If a path did, it would have at least n edges in it, so it would have a cycle. That cycle has strictly positive cost, so we could improve the cost by eliminating the cycle. Therefore, if k ≥ n, we can just cap k at n. Plugging in k = n to the above expression gives the asymptotic runtime of O(mn + n² log n).

Hope this helps!