Dijkstras Algorithm: (Recall) Dijkstra's algorithm assumes that w(e) 20 for each e in the graph maintain a set s of vertices such that Every vertex v ES, d/v/=8(s, v), i.e., the shortest-path from s to v has been found (Intial values: S-=empty, d[s=0 and d[v=ac) (a) select the vertex uev-S such that d/u=min d/x/x Ev-S/ Set S-=sufu (b) for each node v adjacent to u do relax(u, v, w) Repeat step(a)and (b )until S=v 2021/26 CS4335 Design and Analysis of2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 8 Dijkstra’s Algorithm: (Recall) Dijkstra’s algorithm assumes that w(e)0 for each e in the graph. maintain a set S of vertices such that Every vertex v S, d[v]=(s, v), i.e., the shortest-path from s to v has been found. (Intial values: S=empty, d[s]=0 and d[v]=) (a) select the vertex uV-S such that d[u]=min {d[x]|x V-S}. Set S=S{u} (b) for each node v adjacent to u do RELAX(u, v, w). Repeat step (a) and (b) until S=V