For the question below, find out what the mistake is. This dijisktra algorthim s

Question

For the question below, find out what the mistake is. This dijisktra algorthim should represent a bidirectional algorithm. Please provide an explanation once you figure out the mistake.

DIJKSTRA_IN_QUESTION (G=(V,E), w: E -> R, s in V)

foreach v in V do

d[v] = inf // shortest distance found to v

pred[v] = nil // predecessor of v: endpoint of the last edge in a shortest // path to v)

endfor

S ={} // set of vertices whose shortest path is known.

d[S] =0

while(v is not empty) do

for u such that 1) u in V, 2) s in S, and 3) w(s,u) is minimal for all vertices in S

S = S union {u}, V = V - {u}

for each vertex v adjacent to u

if ( v in not in S and d[v] > d[u] + w(u,v))

d[u] = d[u] + w(u,v)

pred[v] = u

end if

end for

end while

END

Explanation / Answer

I have figured out the mistake and completed the whole algorithm which is as follows:

DjikstraAlgo

Input parameters: no, int wt[no][no], strt, fin
Output parameter: ttlLen

PROGRAM bi-directional: big O
Read no, gph, strt, fin;
DEFE=99999; 1
FOR uu=0 to no-1
strtDist[uu]=wt[strt][uu]; no
finDist[uu]=wt[fin][uu]; no
strtVisit[uu]=false; no
finVisit[uu]=false; no
ENDFOR;
strtVisit[strt]=true; 1
finVisit[fin]=true; 1
strtCurr=0; 1
endCurr=0; 1
ttlLen=DEFE; 1
WHILE(strtCurr+endCurr<ttlLen) no/2*(5n+11)
DO strtnxt=0;
strttemp=DEFE;
FOR uu=0 to no-1
IF (the node is not visited by strt node, and strtDist[uu] <strttemp)
THEN strttemp=strtDist[uu];
strtnxt=uu;
ENDIF;
ENDFOR;
strtCurr=strttemp;
strtVisit[strtnxt]=true;
endnext=0;
endtmp=DEFE;
FOR uu=0 to no-1
IF(this node is not visited by fin node, and finDist[uu]<endtmp)
THEN endtmp=finDist[uu];
endnext=uu;
ENDIF;
ENDFOR;
endCurr=endtmp;
finVisit[endnext]=true;
minimum=DEFE;
FOR uu=0 to no-1
IF(minimum>strtDist[uu]+finDist[uu])
THEN minimum= strtDist[uu]+finDist[uu];
ENDIF;
ENDFOR;
IF(minimum<ttlLen)
THEN ttlLen=minimum;
ENDIF;
FOR uu=0 to no-1
IF(this node isn’t visited by strt, and strtDist[uu] >strttemp+wt[strtnxt][uu])
THEN strtDist[uu] =strttemp+wt[strtnxt][uu]
ENDIF;
ENDFOR;
FOR
IF(this node isn’t visited by fin, and finDist[uu] >endtmp+wt[endnext][uu])
THEN finDist[uu] =endtmp+wt[endnext][uu]
ENDIF;
ENDFOR
ENDWHILE;
OUTPUT ttlLen;
END.

Please rate the answer if it helped.......Thankyou

hope it helps....

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.