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

Рассмотрим взвешенный орграф из N вершин с неотрицательными весами на ребрах. Алгоритм Дейкстры находит в этом графе минимальные длины путей от первой вершины до всех остальных.

Будем записывать результат в массив V длины N, значение которого такое же, как и в алгоритме обхода в ширину. Мы будем делить все вершины графа на помеченные и непомеченные. В начале все вершины непомеченные. Для хранения помеченности вершин используем массив Passed из N элементов, i-й элемент которого будет равен true только если i-я вершина помечена. Кроме того, на каждом шаге алгоритма мы будем считать некоторую вершину графа текущей. Вершина будет помеченной, только если она была на каком-либо шаге текущей.

Каждый шаг алгоритма состоит из двух частей:

1. "Улучшение" вершин. Мы рассматриваем текущую вершину и все вершины, из которых есть в нее ребра. Пусть текущая вершина - Cur, и из нее есть ребро в вершину A. Тогда минимальная длина пути из 1 в Cur равна V[Cur], а длина ребра из Cur в A равна G[Cur,A]; значит, длина минимального пути из 1 в A, на последнем шаге проходящего через Cur, равна V[Cur]+G[Cur,A]; если это число меньше чем V[A] или V[A]=-1, то мы запишем это число в V[A].

2. Выбор новой текущей вершины. Мы выбираем новую текущую вершину как вершину с минимальным значением V из всех непомеченных вершин i, для которых V[i]<>-1; таким образом, новая текущая вершина будет на данный момент самой близкой к 1 из непомеченных.

Алгоритм заканчивает свою работу, когда мы не сможем выбрать текущую вершину.

Реализация алгоритма:

const
  MaxN = 100;

var
  N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Integer;
  V : array [1 .. MaxN] of Integer;

procedure Djkstra(A : Integer);
var
  B : integer;
  Passed : array [1 .. MaxN] of Boolean;
  Cur : integer;
begin
  fillchar(Passed,sizeof(Passed),0);
  fillchar(V,sizeof(V),255);
  Cur := A;
  V[cur] := 0;
  repeat
    Passed[Cur]:=true;
    for B:=1 to N do
      if (G[Cur,B]<>-1) and ((V[b]=-1) or (V[b]>V[Cur]+G[Cur,B])) then
        V[b]:=V[Cur]+G[Cur,B];
    Cur := 0;
    for B:=1 to N do
      if (not Passed[b]) and (V[b]<>-1) and ((Cur=0) or (V[Cur]>V[b])) then
        Cur := B;
  until Cur=0;
end;