Solution to 1. State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge weights. - Sikademy
Author Image

Archangel Macsika

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]\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\isinV-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} A& &B&& C &&D&&E\\ 0 & &INF&&INF&&INF&&INF\\ &&10&&3&&INF&&INF\\ && 7&& &&11&&5\\ &&7&&&&11&&\\ &&&&&&9\\ \end{matrix}

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

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\isinV-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} A& &B&& C &&D&&E\\ 0 & &INF&&INF&&INF&&INF\\ &&10&&3&&INF&&INF\\ && 7&& &&11&&5\\ &&7&&&&11&&\\ &&&&&&9\\ \end{matrix}

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


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3812-qpid-2511