Алгоритм Дейкстри

Алгоритм Дейкстри (E.W. Dijkstra, 1959)

1)  присвоїти всім вершинам мітку ∞;

2)  серед ще непереглянутих вершин знайти вершину j з найменшою міткою;

3)  для кожної необробленої вершини i: якщо шлях до вершини i через вершину j менший існуючої мітки, замінити мітку на нову відстань;

4)  якщо залишилися необроблені вершини, перейти до кроку 2;

5)  мітка = мінимальна відстань.

Масиви та множини:

• Множина vv, до якої включено ще не розглянуті вершини.
• масив dist, такий, що dist[i] – довжина поточного найкоротшого шляху із заданої вершини x до вершини i;
• масив from, такий, що from[i] – номер вершини, із якої потрібно йти до вершини i в цьому найкоротшому шляху.

Ініціалізація:

• заповнюємо масив d нулями (вершини не оброблені);
• записати в dist[i] значення d[x,i];
• заповнити масив from значенням x;
• записати a[x]=1.

Реалізація мовою Pascal

 Const Nmax=100;

procedure TForm1.Button1Click(Sender: TObject);

var n, p, k : Integer;

    d:array[1..Nmax, 1..Nmax] of Integer;

    dist,from:array[1..Nmax] of integer;

    a, b, c, r, x, i, j : Integer;

    s:string;

    flag : Boolean;

    vv:set of byte;

    min,start,finish:integer;

begin

        //Читаємо кількість вузлів графу

        n := StrToInt(Memo1.Lines[0]);

        //Заповнюємо матрицю суміжності

        //

        for i:=1 to n do begin

         dist[i]:=0;

         from[i]:=0;

         for j:=1 to n do begin

           d[i,j]:=0;

         end;

        end;

        For i := 1 To Memo1.Lines.Count - 1 do begin

           s := Memo1.Lines[i];

           s := Trim(s);

           while pos('  ', s)<>0 do delete(s,pos('  ',s),1);

           If (s <> '') and (pos(' ',s)<>0) Then begin

                x := pos(' ',s);

                a := StrToInt(copy(s,1,x-1));

                delete (s,1,x);

                x := pos(' ' ,s);

                b := StrToInt(copy(s,1,x-1));

                c := StrToInt(copy(s,x+1,Length(s)-x));

                d[a, b] := c;

                d[b, a] := c;

           end;

        end;

        //Перед пошуком здійснюємо початкові налаштування - ініціалізацію

        //Читаємо номер початкової вершини

        start:=StrToInt(Edit1.Text);

        //Читаємо номер кінцевої вершини

        finish := StrToInt(Edit2.Text);

        vv:=[1..n];

        vv:=vv-[start];

        for i:=1 to n do begin

            if d[start,i]=0 then

                dist[i]:=65535

            else

                dist[i]:=d[start,i];

            from[i]:=start;

        end;

        from[start]:=0;

        dist[start]:=0;

        //Починаємо пошук шляху

        while vv<>[] do begin

            min:=65535;

            for i:=1 to n do begin

              if (i in vv) and (dist[i] < min) and (dist[i] > 0) then begin

                min:=dist[i];

                k:=i;

              end;

            end;

            for i:=1 to n do begin

              if (d[k,i]>0) and (dist[i]>dist[k]+d[k,i]) then begin

                dist[i]:=dist[k]+d[k,i];

                from[i]:=k;

              end;

            end;

            vv:=vv-[k];

        end;

        //Виведення шляху

        i:=finish;

        s:=' -> '+IntToStr(finish);

        //Memo2.Lines.Add(IntToStr(finish));

        while i<>start do begin

           s:=' -> '+IntToStr(from[i])+s;

           //Memo2.Lines.Add(IntToStr(from[i]));

           i:=from[i];

        end;

        Edit3.Text:=s;

end;