Finding the shortest path in a colored graph

Question

The problem I am trying to solve is:

Given a graph where each edge is colored in either red or blue:

a) Give an algorithm that produces the path that between two vertices (s,t) that goes over a minimal amount of red edges.

b) Give an algorithm that produces the path that between two vertices (s,t) that goes over a minimal amount of blue edges, out of all the paths that go from s to t that pass through a minimal amount of red edges.

So far: For a) I can use a modified BFS algorithm. When looking at a vertex, v, put all the vertices that are connected by a blue edge to v first in the queue, and then add the rest to the end of the queue. Thus, the first time the algorithm will encounter t will be the path in question.

How do I prove correctness of this algorithm? It seems very greedy. How do I expand this to answer b)?

Thanks for your time.

Answer 1

There are two important details about your algorithm that you need to keep in mind:

1. Nodes can be added to the queue multiple times in your scenario. You are only allowed to explore them once, though. You can enforce that by maintaining a boolean flag per node that tells you whether you have already explored a node.
2. You can only stop the algorithm as soon as you take t out of the queue, not as soon as you put it in.

If you do it this way (and your question doesn't indicate you don't), your algorithm is indeed correct.

How do I prove correctness of this algorithm?

If you assign edge weight 1 to red edges and edge weight 0 to blue edges, the problem reduces to find the shortest path in the transformed graph. Let's apply Dijkstra to this problem. I will show that your algorithm in fact implements Dijkstra, which proves its correctness.

We can show that we only ever have nodes of two different distances in the priority queue: If m is the minimum distance of a node in the priority queue, then we can't have a node of distance m + 2 in the queue, because that would mean that we must already have explored a node with distance m + 1, which is impossible because we explore nodes in order of increasing distance.

Your modified BFS in fact implements the Dijkstra algorithm using a double-ended queue as the 2-value priority queue: If Q is your queue, then there is an index i, such that Q[1..i] contains only nodes of distance m and Q[i+1..] contains only nodes of distance m + 1.

How do I expand this to answer b)?

You can extend the concept by maintaining a 4-value priority queue, for example implemented as two double-ended queue. One queue will hold nodes of distance m red edges, the other will hold nodes of distance m + 1 red edges. Both are ordered by increasing number of blue edges (there will also only be two different distance values in each of these).

Answer 2

[[The algorithm mentioned is correct if you put nodes adjacent to blue edges in front of queue instead of end of the queue as discussed in comment.]]

For problem (B) just discard the edges which are not in original shortest path(which uses minimum red edges). Its easy to find if a edge u-v is in shortest path. u-v is in shortest path if distance[source][u]+cost[u][v]+distance[v][destination]=distance[source][destination]. After discarding extra edges rest of the task is easy.