How to implement the Dijkstra algorithm in Pascal?

Question

I’m trying to implement Dijkstra’s algorithm, creating a Pascal function.

I have something like:

function Dijkstra(L:mapa):integer;
begin
   min := max ;
   map.mini:= 0;
   for i := 2 to min do
      if L.matriz[i,j] < map.mini then
         begin
            min:= L.matriz[i,j];
            map.mini := i;
         end;
      Dijkstra:=map.mini ;
end;

How far I’ve come isn’t working, any suggestions?

Answer 1

I found this answer in the book PASCAL STRUCTURED 3
Edition Editora LTC 1999
Of the authors :
Harry Farrer
Christiano Gonçaves Becker
Eduardo Chaves Faria
...

Example 2.27 page 77..

The nodes in the graphic presented below represent the cities and the arches the presence of a road linking two cities the numbers beside the Arches represent the distance in kilometers.

This graph can be represented numerically by a two-dimensional composite variable ,in which the distance between two cities i,j is indicated by the element D(i,j; if i=j or if there is no connection between i and i. D(i.i) will be zero. That way you get:

The problem is, then, to find the shortest way between any two cities. This problem was solved by Dijkistra [DIJKISTRA, 1971] and has a number of application optimization issues.
In addition to the distance matrix D, the one-dimensional composite variable DA is considered, whose DA[I] component represents the accumulated distance on a journey since the origin to city I. Each of these components will be started with a very large value, for example 10000.

Two more one-dimensional composite variables will still be considered. The first, called Ant, will be such that its component Ant[I] indicates which is the antecedent city of I on the path considered. The other Expa will have "expanded logical components".
Starting from a city C initially equal to the origin, the new cumulative distance (Novada) of each of the cities adjacent to C not yet expanded is calculated. The new cumulative distance will prevail over the previous value if it is lower, in this case ,C will be assigned the Ant[I] component. When the C expansion is complete, it is recorded that Expa[C] is true.
Then, we look, 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 then the smallest that can be achieved from the Origin.
The process will be repeated until City C is Destiny or no city has yet been expanded, with a cumulative distance of less than 10000. In the latter case, this means that there is no path connecting Origin to Destiny.

Here is the algorithm in Pascal language:

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.