Алгоритм Дейкстеры – поиск минимального пути на графе при не отрицательных весах ребер

Итак, пусть граф задан матрицей смежности.

Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими “бесконечность”. По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.

Еще один линейный массив done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

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

Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше – ведь веса всех ребер графа у нас положительны. Таким образом:

Delphi/Pascal

dist[s]:= 0; done[s]:= true; last:= s;

1

dist[s]:= 0; done[s]:= true; last:= s;
Повторить N-1 раз следующие действия:
1. для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:
  
  Delphi/Pascal
  
  dist[x]:= min(dist[x], dist[last]+ sm[last,x]);
  
  1
  
  dist[x]:= min(dist[x], dist[last]+ sm[last,x]);
2. среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last ;
3. пометить эту новую вершину в массиве done.

Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.

dist[s]:= 0; 
done[s]:= true; 
last:= s;
for i:= 1 to N-1 do
	begin
		for x:= 1 to N do
			if (sm[last,x]&lt;&gt;0)and(not done[x])
				then dist[x]:= min(dist[x],dist[last]+ sm[last,x]);
		min_dist:= MaxLongInt;
		for x:= 1 to N do
			if (not done[x])and(min_dist&gt;dist[x])
				then begin min_dist:= dist[x];
							  last:= x;
						end;
		done[last]:= true;
	end.

dist[s]:= 0;

done[s]:= true;

last:= s;

for i:= 1 to N-1 do

begin

for x:= 1 to N do

if (sm[last,x]<>0)and(not done[x])

then dist[x]:= min(dist[x],dist[last]+ sm[last,x]);

min_dist:= MaxLongInt;

for x:= 1 to N do

if (not done[x])and(min_dist>dist[x])

then begin min_dist:= dist[x];

last:= x;

end;

done[last]:= true;

end.

Также…

Теория на Вики

Моя реализация (пока что на коленке)

Дейкстера, поиск минимального пути в графе (сам путь и его стоимость в моей реализации). Пусть есть граф, заданный матрицей смежности AAdjencyMatrix, размером ASizeOfMatrix. Необходимо найти минимальное расстояние и сам минимальный путь от одной вершины к другой. Я сделал это так… Код не тестил, на уровне идеи…

procedure TMain.Dijkstra(

    AAdjencyMatrix: TAdjencyMatrix; // square adjency matrix of Graph
    AsizeOfAdjMatrix, // size of matrix
    Anode1, // node 1
    Anode2: integer; // node 2
    var minDistance:integer;  // out Param
    var path:string // out Param

);


        function min(a,b:integer):integer;
        begin
        if a>b then min:=b
        else min:=a;
        end;


var
    x:integer;
    distArray:TArray<longInt>;
    i: integer;
    last:integer;
    done:TArray<Boolean>;

const INF=MaxLongInt;

begin

    // init dist array
    setlength(distArray,AsizeOfAdjMatrix);
    for i :=0 to High(distArray) do distArray[i]:=MaxLongInt;

    // init done array
    setlength(done,AsizeOfAdjMatrix);
    for i :=0 to High(done) do done[i]:=false;

    // init first node
    distArray[Anode1]:=0;
    done[Anode1]:=true;
    last:=Anode1;

    path:=last.ToString();

    for i:=1 to N-1 do begin // N-1 because we stay in Anode1


      for x:=1 to N do

        if (AAdjencyMatrix[last,x]<>0) and (not done[x])  // counting distances to incident nodes
        then distArray[x]:=min(distArray[x],distArray[last]+AAdjencyMatrix[last,x]);


          minDistance:=MaxLongInt;
          for x:=1 to N do
          if (not done[x]) and (minDistance>distArray[x]) // searching min beetwen undone
          then
          begin
          minDistance:=distArray[x];
          last:=x;
          end;

          path:=path+','+last.ToString();

          {
              write('na dannii moment min distanciya= ',minDistance,' ot verwini ',s,' do verwini ',last,' ');
    done[last]:=true;
    path:=path+','+last;
    writeln;

          }

          if last=Anode2 then
          begin

           ShowMessage(

            'path='+path+','
            +'min_distance='+minDistance.ToString

           );

          //writeln('ves puti ot ', s,' do ', q,' = ',min_dist) ;
          //break;
          end;



    end;


//

end;

procedure TMain.Dijkstra(

AAdjencyMatrix: TAdjencyMatrix; // square adjency matrix of Graph

AsizeOfAdjMatrix, // size of matrix

Anode1, // node 1

Anode2: integer; // node 2

var minDistance:integer; // out Param

var path:string // out Param

);

function min(a,b:integer):integer;

begin

if a>b then min:=b

else min:=a;

end;

var

x:integer;

distArray:TArray<longInt>;

i: integer;

last:integer;

done:TArray<Boolean>;

const INF=MaxLongInt;

begin

// init dist array

setlength(distArray,AsizeOfAdjMatrix);

for i :=0 to High(distArray) do distArray[i]:=MaxLongInt;

// init done array

setlength(done,AsizeOfAdjMatrix);

for i :=0 to High(done) do done[i]:=false;

// init first node

distArray[Anode1]:=0;

done[Anode1]:=true;

last:=Anode1;

path:=last.ToString();

for i:=1 to N-1 do begin // N-1 because we stay in Anode1

for x:=1 to N do

if (AAdjencyMatrix[last,x]<>0) and (not done[x]) // counting distances to incident nodes

then distArray[x]:=min(distArray[x],distArray[last]+AAdjencyMatrix[last,x]);

minDistance:=MaxLongInt;

for x:=1 to N do

if (not done[x]) and (minDistance>distArray[x]) // searching min beetwen undone

then

begin

minDistance:=distArray[x];

last:=x;

end;

path:=path+','+last.ToString();

{

write('na dannii moment min distanciya= ',minDistance,' ot verwini ',s,' do verwini ',last,' ');

done[last]:=true;

path:=path+','+last;

writeln;

}

if last=Anode2 then

begin

ShowMessage(

'path='+path+','

+'min_distance='+minDistance.ToString

);

//writeln('ves puti ot ', s,' do ', q,' = ',min_dist) ;

//break;

end;

Реализация Дениса Кряжева

program Alg_Deikstri;
uses crt;
const
n=6;
var
file_source, file_res:text;
sm:array[1..n,1..n] of byte;
dist,cep:array[1..n] of integer;
done:array[1..n] of boolean;
s,last,i,j,q,x,min_dist:integer;

function min(a,b:integer):integer;
begin
if a>b then min:=b
else min:=a;
end;

begin
clrscr;
assign(file_source,'f:\bp\bin\zadacbi\source.txt');
reset(file_source);
for i:=1 to n do
for j:=1 to n do
read(file_source,sm[i,j]);
writeln('massiv 1:');
for i:=1 to n do
begin
for j:=1 to n do
write(sm[i,j],' ');
writeln;
end;

for i:=1 to n do dist[i]:=100;
writeln('vvedite nomera na4alnoi verwini i kone4noi');
readln(s,q);
dist[s]:=0;
done[s]:=true;
last:=s;
for i:=1 to N-1 do
begin
writeln;
writeln('obxod verwini ',last);
for x:=1 to N do
if (sm[last,x]<>0)and(not done[x])
then dist[x]:=min(dist[x],dist[last]+sm[last,x]);

min_dist:=32677;
for x:=1 to N do
if (not done[x])and(min_dist>dist[x])
then
begin
min_dist:=dist[x];
last:=x;
end;
write('na dannii moment min distanciya= ',min_dist,' ot verwini ',s,' do verwini ',last,' ');
done[last]:=true;
writeln;
if last=q then
begin
writeln('ves puti ot ', s,' do ', q,' = ',min_dist) ;
break;
end;
end;
readln;
end.

Виктор Дож Матузенко, спс за ссылки.

сам добил её)

program Alg_Deikstri;

uses crt;

const

n=6;

var

file_source, file_res:text;

sm:array[1..n,1..n] of byte;

dist,cep:array[1..n] of integer;

done:array[1..n] of boolean;

s,last,i,j,q,x,min_dist:integer;

function min(a,b:integer):integer;

begin

if a>b then min:=b

else min:=a;

end;

begin

clrscr;

assign(file_source,'f:\bp\bin\zadacbi\source.txt');

reset(file_source);

for i:=1 to n do

for j:=1 to n do

read(file_source,sm[i,j]);

writeln('massiv 1:');

for i:=1 to n do

begin

for j:=1 to n do

write(sm[i,j],' ');

writeln;

end;

for i:=1 to n do dist[i]:=100;

writeln('vvedite nomera na4alnoi verwini i kone4noi');

readln(s,q);

dist[s]:=0;

done[s]:=true;

last:=s;

for i:=1 to N-1 do

begin

writeln;

writeln('obxod verwini ',last);

for x:=1 to N do

if (sm[last,x]<>0)and(not done[x])

then dist[x]:=min(dist[x],dist[last]+sm[last,x]);

min_dist:=32677;

for x:=1 to N do

if (not done[x])and(min_dist>dist[x])

then

begin

min_dist:=dist[x];

last:=x;

end;

write('na dannii moment min distanciya= ',min_dist,' ot verwini ',s,' do verwini ',last,' ');

done[last]:=true;

writeln;

if last=q then

begin

writeln('ves puti ot ', s,' do ', q,' = ',min_dist) ;

break;

end;

readln;

end.

Виктор Дож Матузенко, спс за ссылки.

сам добил её)

Алгоритм Дейкстеры – поиск минимального пути на графе при не отрицательных весах ребер

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

Реализация

Моя реализация (пока что на коленке)

Реализация Дениса Кряжева

MY PROJECTS

Recent Posts

Categories