I found this answer in PASCAL STRUCTURED 3 book
Publisher Edition LTC 1999
Two authors:
Harry Farrer
Christiano Gonçaves Becker
Eduardo Chaves Faria
...
Example 2.27 page 77 ..
The nodes in the chart below represent cities and arcs the presence of a road linking two cities the numbers next to the arcs represents the distance in kilometers.
Thisgraphcanberepresentednumericallybyatwo-dimensionalcompositevariableinwhichthedistancebetweentwocitiesi,jisindicatedbytheelementD(i,j,ifi=jorifthereisnoconnectionbetweeniei.D(ii)willbezero.Thiswaywehave:
Theproblemisthentofindtheshortestpathbetweenanytwocities.ThisproblemwassolvedbyDijkistra[DIJKISTRA,1971]andhasanumberofapplicationoptimizationissues.InadditiontotheDmatrixofdistances,weconsidertheone-dimensionalcompositevariableDA,whoseDAcomponent[I]representstheaccumulateddistanceonapathtraveledfromtheorigintocityI.Eachofthesecomponentswillstartwithaverylargevalue,forexample10000.
Twomoreone-dimensionalcompositevariableswillstillbeconsidered.Thefirstone,calledAnt,willbesuchthatitsAnt[I]componentindicateswhichistheantecedentcityofIintheconsideredpath.TheotherExpA,willhave"expanded" logical components.
Starting from a city C initially equal to its origin, we calculate the new accumulated distance (NovaDA) of each of the cities adjacent to C not yet expanded. The new accumulated distance will prevail over the previous value if it is lower, in which case C will be assigned the Ant [I] component. When the expansion of C is finished, it is recorded that ExpA [C] is true.
Next, one searches for, among the cities not yet expanded, those that have the smallest accumulated distance. This will be the new city C, and its accumulated distance is therefore the lowest that can be achieved from the Source.
The process will be repeated until city C is Destination or there is no city as yet unexpanded, whose accumulated distance is less than 10000. In the latter case, this means that there is no path linking Origin to Destiny.
Here is the algorithm in Pascal:
program Dijkistra;
var D: array[1..100, 1..100] of integer;
DA, Ant: array[1..100] of integer;
ExpA: array[1..100] of boolean;
N, Origem, Destino, I, J, C, NovaDA, Min: integer;
begin
readln(N);
for I:= 1 to N do
begin
for J:= 1 to N do
read(D[I,J]);
readln;
end;
readln(Origem, Destino); { atribuição de valores iniciais necessários}
for I:= 1 to N do
begin
ExpA[I]:= false;
DA[I]:= 10000
end;
C:= origem;
DA[C]:= 0;
while (C <> Destino) and(C <> 0) do
begin {Expanção de C}
for I:= 1 to N do
if (D[C, I] <> 0) and(not Expa[i])
then begin
NovaDA:= DA[C] + D[C, I];
if NovaDA < DA[I]
then begin
DA[I]:= NovaDA;
Ant[I]:= C
end
end;
Expa[C]:= true; {Determinação do proximo C}
Min:= 10000;
C:= 0;
for I:= 1 to N do
if (not ExpA[I]) and (DA[I] < Min)
then
begin
Min:= DA[I];
C:= I;
end;
end;
if C = Destino
then begin
writeln('Caminho mais curto');
writeln(C);
while C <> Origem do
begin
C:= Ant[C];
writeln(C)
end
end
else writeln('Não existe caminho unindo as duas cidades');
end.