How to implement the Dijkstra algorithm in Pascal?

2

I'm trying to implement the Dijkstra algorithm by creating a function in Pascal.

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;

As far as I get, it's not working, any suggestions?

    
asked by anonymous 15.11.2014 / 13:17

1 answer

1

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.
    
06.09.2015 / 19:33