Dijkstra's algorithm to find shortest path

Question

A particular state has a set of E roads among its set of V cities, where the time to traverse the road from city u to a neighbor city v is given by cuv. (Note that cuv need not equal cvu – in fact there may be no road from v to u.) After a snowstorm, some of the roads are impasable, but the governor needs to drive from city s to city t very soon, so soon that there is time to clear only one of the impassable roads. Give an O(E log V ) algorithm that determines which road to plow (one only) in order to achieve the minimum possible time path from a city s to city t. The input is a list of all the roads, the values cuv for each road, s, t, and the set of impassable roads. If road clearing is of no help, the algorithm should say so.

I think the closest way to approach to this question is using Dijkstra's algorithm to find the shortest path, however, since we don't know which road is impassable and which road is passable, Dijkstra's algorithm seems inappropriate for this question. So, is there any other algorithm that able to check the condition of each edge and find the shortest path? Sorry about my logic, I don't understand this question very well, any response or hints will help, thanks.

Could someone explain how my question is similar to Shortest path between two vertices when exactly one edge weight can be reduced by 50%?

Answer 1

Let's call the given graph G(V, E), where E can be split into D + F, where D represents the passable and F the impassible roads.

As suggested in comments, duplicate the graph, so you have G(V,D) and G'(V',D'). For any given vertex u ∈ V, there is a "copy" vertex u' ∈ V'. And so there is also an s' and a t'. We do not include F or F' at this point.

Then define a set of edges F° as (u,v'), for each edge (u,v) ∈ F. So these edges in F° are passable connections from V to V' -- in that direction only.

Let's call this new graph, G°(V°, E°), where V° = V + V', E° = D + D' + F°, and F° as defined in the previous paragraph.

Now solve the problem of going from s to {t, t'} in G°. As there are no edges from V' to V, a solution path ending in t' will only use one edge (u,v') from F°. Note that if t is reached via a shorter path than t', this means that no edge from F° is used (no impassable road needs to be plowed).

The problem of finding the shortest path between s and {t, t'} in G° is now a standard problem that can be solved with Dijkstra's algorithm. One additional thing is needed: For each visited w' ∈ V', the edge (u,v') from F° -- that was crossed to get there -- needs to be logged. This information should just get passed on to the next vertex that the algorithm visits, so that when t' is finally found, the answer can be given immediately, i.e. that edge (u,v').

The number of edges visited in this algorithm is at most |E°| = |D + D' + F°| ≤ 2|E| = O(|E|). The algorithm visits every edge only once, so the time complexity is O(|E|).

Answer 2

You can try to approach this question as follows:

You can maintain an array dist[n][2], where n is the number of vertices. where

dist[i][0] represents shortest time needed to travel to reach i without clearing any road that has snow on it

dist[i][1] represents shortest time needed to travel to reach i by clearing one road from source to i that has snow on it.

Now the data structure that can be used to solve this is queue. The algorithm is mentioned below.

1. Insert your source vertex into the queue and mark it as zero.          //marking 0 helps us to know that no roads has been cleared yet.
2. Do while queue is not empty
    2.1 Pop element from queue. Let it be x.
    2.2 For all the vertices i connected to x
        dist_without_clearing = dist[x][0] + cxi
        dist_with_clearing = dist[x][1] + cxi
        dist_with_clearing = min(dist_with_clearing,dist[x][0] + cxi)    // here only the roads that are covered with snow needs to be considered.
        if(dist_without_clearing < dist[i][0]) 
            insert(i,0) in queue
            dist[i][0] := dist_without_clearing
        endif
        if(dist_with_clearing < dist[i][1])
            insert(i,1) in queue.
            dist[i][1] := dist_with_clearing
        endif
3. Return min(dist[destination][0], dist[destination][1]) as your answer.