Question

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

Answer 1

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} 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}