Dijkstras algorithm is applied to a rectangular grid of size n times n. The vertices of the rectangular grid have the form (i,j), where i,j=1,2,3,,n, and the edges (all of unit length) connect pairs (i,j), (i+1,j) and (i,j), (i,j+1). Assume that vertex (1,1) is the source. What are the optimal paths recovered by the algorithm? What are the final values of arrays D and P? In the case of ambiguity assume that the algorithm makes choices according to lexicographic ordering of vertices, I.E. (i₁,j₁) < (i₂,j₂) if and only if i₁ < i₂ or (i₁ = i₂ and j₁ < j₂).

procedure Dijkstra; begin S := {1}; for i := 2 to n do begin D[i] := C[1,i]; P[i] := 1 end; for i := 1 to n-1 do begin choose a vertex w in V-S such that D[w] is minimum; add w to S; for each vertex v in V-S do if D[v] > D[w] + C[w,v] then begin D[v] := D[w] + C[w,v]; P[v] := w end end end;