DAA(Design Analysis & Algorithms) B.tech 6th sem
Dijkstra’s algorithm 1. Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (G, v) for the case in which all edge weights are nonnegative. 2. Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. Initialize Algorithm:- Relax Algoritham:- Example of Relax algorithm Relaxing an edge (u, v) with weight w(u, v)=2. The shortest-path estimate of each vertex appears within the vertex. a a) Because v.d > u.d + w(u, v) prior to relaxation, the value of v.d decreases. b) b) Here v.d <=u.d + w(u, v) before relaxing the edge, and so the relaxation step leaves v.d unchanged.