Question

Explain the loop invariant in dijkstra's algorithm

Answer 1

Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative.

In the algorithm below:
S = the set of vertices whose shortest path from the source have been found
Q = V-S (at the start of each iteration of the while loop)


DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = \emptyset
Q = V[G]
while Q \neq \emptyset
do u = EXTRACT-MIN(Q)
S = S \cup {u}
for each vertex v \in Adj[u]
do RELAX(u, v, w)

Hope it helped you
------------------------------