1. State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge weights.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
d[s] 0
For each v V-{s}
do d[v] infinity
S
Q V
While Q#
do u Extract-min(Q)
S SU{u}
for each v Adj[u]
do if d[v]>d[u]+w(u,v)
Then d[v] 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 vV-S whose distance estimate S is minimal
3) Update the distance estimates of vertices adjacent to v
4)S 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:
S={A,C,E,B,D}
d[s] 0
For each v V-{s}
do d[v] infinity
S
Q V
While Q#
do u Extract-min(Q)
S SU{u}
for each v Adj[u]
do if d[v]>d[u]+w(u,v)
Then d[v] 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 vV-S whose distance estimate S is minimal
3) Update the distance estimates of vertices adjacent to v
4)S 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:
S={A,C,E,B,D}