Answer to Question #128829 in Discrete Mathematics for aamina

Question #128829
1. State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge weights.
1
Expert's answer
2020-08-10T18:20:04-0400

d[s]"\\gets" 0

For each v"\\isin" V-{s}

do d[v]"\\gets" infinity

S"\\gets" "\\varnothing"

Q"\\gets" V

While Q#"\\varnothing"

do u"\\gets" Extract-min(Q)

S"\\gets" SU{u}

for each v"\\in" Adj[u]

do if d[v]>d[u]+w(u,v)

Then d[v]"\\gets" d[u]+w(u,v)


1)Maintain set S of vertices whose shortest path distances from S are known

2)At each step add to S the vertex v"\\isin"V-S whose distance estimate S is minimal

3) Update the distance estimates of vertices adjacent to v

4)S"\\gets" SU{u}

Add u to set of vertices, u is the shortest distance from s

5)Each vertices v from u

If distance of vertices is greater than addition of distance of u and weight of u,v

Then distance of v =addition of distance of u and weight of u,v

Example




Q:"\\begin{matrix}\n A& &B&& C &&D&&E\\\\\n 0 & &INF&&INF&&INF&&INF\\\\\n &&10&&3&&INF&&INF\\\\\n && 7&& &&11&&5\\\\\n &&7&&&&11&&\\\\\n \n &&&&&&9\\\\\n\n\\end{matrix}"

S={A,C,E,B,D}


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS