title: Shortest path in absence of the given edge
body: <p>Suppose we are given a weighted graph G(V,E).</p>
  
  <p>The  graph contains <strong>N</strong> vertices (<em>Numbered from 0 to N-1</em>) and <em>M Bidirectional edges</em> .</p>
  
  <p>Each <em>edge(vi,vj)</em> has <em>postive distance d</em> (ie the distance between the two vertex vivj is d)</p>
  
  <p>There is <em>atmost one edge between any two vertex</em> and also there is <em>no self loop</em> (ie.no edge connect a vertex to
  itself.)</p>
  
  <p>Also we are given <strong>S</strong> the source vertex and <strong>D</strong> the destination vertex.</p>
  
  <p>let <strong>Q</strong> be the number of queries,each queries contains one  edge <strong>e(x,y)</strong>.</p>
  
  <p>For each query,We have to find the <strong>shortest path from the source S to Destination D, assuming that  edge (x,y) is absent in original graph.</strong>
  If no any path exists from S to D ,then we have to print No.</p>
  
  <p><em>Constraints are high 0&lt;=(N,Q,M)&lt;=25000</em> </p>
  
  <p><strong>How to solve this problem efficiently?</strong></p>
  
  <p><strong>Till now</strong> what i did is implemented the  simple <em>Dijakstra algorithm.</em></p>
  
  <p>For each Query Q ,everytime i am <em>assigning (x,y) to Infinity</em> 
  and <em>finding Dijakstra shortest path</em>.</p>
  
  <p>But this approach will be very slow as overall complexity will be <em>Q</em>(time complexity of Dijastra Shortes path)*</p>
  
  <p>Example::</p>
  
  <pre><code>N=6,M=9
  S=0 ,D=5
  
  (u,v,cost(u,v))
  0 2 4
  3 5 8
  3 4 1
  2 3 1
  0 1 1
  4 5 1
  2 4 5
  1 2 1
  1 3 3
  
  Total Queries =6
  
  Query edge=(0,1) Answer=7
  Query edge=(0,2) Answer=5
  Query edge=(1,3) Answer=5
  Query edge=(2,3) Answer=6
  Query edge=(4,5) Answer=11
  Query edge=(3,4) Answer=8
  </code></pre>