GATE CSE
First time here? Checkout the FAQ!
x
+9 votes
451 views

For the graph given below Dijkstra’s algorithm does not provide correct shortest path tree.

Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra’s provide the correct shortest path tree where the values of edge (Q to S) ∈ [–20, 20] and ‘P’ is the source vertex are ______.

asked in Algorithms by Active (1.8k points)  
retagged by | 451 views
[ -20 ,-1 ] and [ 11,20 ] are allowed .(30 values)

@PRIYA SHANKAR  what is the solution provided by made easy ?

As PQ is comman path, lets eleminate it.

Now, QTUW path is 12. But, inorder that I select the next relaxing edge as WV, QS path must be greater than 12.

So, [13 20] is one valid range.

=========================

Next, consider min shortest path in original diagram QTUWVS. Path length is 2.

Now, if I use QS as 2, still it would give me one of the correct shortest paths. If QS is less than 2, still it would work.

So, other range is [-20 2].

===========================

So, total 31 values.

2 Answers

+5 votes
Best answer

I am getting [-20 to -1] and [13 to 20] total 28 values.

answered by Veteran (14.7k points)  
selected by
Also try for 11,12..
Take QS = 11, Then V will hold = 14 and w is holding = 13 (See, we are just holding the values, not finalized them yet)

Now, who will work first w = 13 as it is small .

Now, it updates V = 2 which previously had 14 but it was not finalized and now 2 is minimum. It is finalized.
V holds 14 means S is relaxed with distance value 12. ( P->S crossing the maximum of 3)
-ve edge is not in cycle .so dijkstra should provide correct shortest path. correct me if i am wrong
yes you are right, bcoz finally w will be rested and we get correct path.
+4 votes

Lots of corner cases : although I tried to explain in the following way :

This problem involves many situations where two same minimum distance nodes occur while running the Dijkstra algorithm.

There are two critical distances $P -> S \text {  and  } P -> V$

Assume QS edge cost as = $\begin{align*} x \end{align*}$

From direct observation we can see that shortest path from P to S can be 3 or less and shortest distance from P to V can be 2 or less. ( can go to negative ) ( from P distances 3 and 2 exist via W to S and V respectively )

Well, if we allow large negative value of edge cost of QS then S and V also will be relaxed at some negative distance away from P. This is fine according to our condition.Let's start using negative values of x starting from -20. 

If we use the two constraint imposed on $\text{max} \text{ dist(P,V)}$ and $\text{max} \text{ dist(P,S)}$ then;

$$\begin{align*} &\text{ dist(P,V)} \leq 2 \text{ AND} \text{ dist(P,S)} \leq 3 \\ &=> 1+x+2 \leq \text{max(dist(P,V))} = 2 \ \ \text{ AND } \ \ 1+x \leq \text{max(dist(P,S))} = 3\\ &=> \text{x}\leq \text{-1} \\ \end{align*}$$

Now in the range of $\begin{align*} [-20,-1] \end{align*}$ if we run the Dijkstra's algorithm, then S and V will be removed early (Relaxed or no update further possible) and luckily no distance conflict with vertices S and V arise towards the end of the algorithm. They remain below their maximum limit which are 3 and 2 respectively.


Now we will start assigning positive value to the edge cost of QS. For positive values of $x$ vertices S and V will also end up being relaxed at some positive value of distances. Here we have to be carefull because, their +ve distances can not increase beyond certain limit as mentioned earlier.

Now if we don't Relax them (S and V) early in the running algorithm (or, retain their updating possibility towards the end) , then we must also have to keep them (without the chance of being relaxed) till the end such that their distances can be correctly updated (to 3 and 2) using W or via W.

How can we keep them (vertices S and V ) in the algorithm without relaxing early.

Note that we can not intentionally keep them (S and V) unused (unrelaxed) nodes if in a particular step their distance become the minimum. 

So, the point is if some vertices are not relaxed towards the end, that means their distance value are more than the currently existing large value of distance (of not relaxed nodes).***$\textbf{[1]}$

So, We conclude that S and V can only be relaxed after W has been relaxed.

Now we know that the shortest path from P to W is of distance 13. So, during Dijkstra's relaxing rounds of vertices, to keep both of S and V unrelaxed then;

$$\begin{align*} & 1+x > 13 \ \ \ \text{AND}, \ \ \ 1+x+2 > 13 \\ &=> x > 12 \end{align*}$$

So from

$$\begin{align*} x = 13 \text{  to  } x = 20 \end{align*}$$

we will have no issue of S and V getting Relaxed before W.

Final Ranges of edge cost of QS is $\begin{align*} [-20,-1] \ \ \text{ and  } [13,20] \\ \end{align*}$ 


***PS$\textbf{[1]}$: [ little bit exception to this statement : for x = 10,11.etc.  S is not relaxed although its distance value (11,12 etc) is less than 18 of U, because at that time T is also present having the value 4, so T was selected ]

$[\textbf{2}]$ : I haved assumed one criteria: when two or more vertices with same distance occur while running the Dijkstra's algorith ,it could select any one of them for relaxing.

 http://stackoverflow.com/questions/9264799/dijkstras-algorithm-what-to-do-if-there-are-two-or-more-nodes-with-minimal-wei

answered by Veteran (50.5k points)  
edited by
I explained the same above in my posted pic :P :P

But nobody gave a dammn! uhh!!
May be Your pic is not readable.  But as soon as i found same i gave +1


Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,108 comments
29,272 users