Алгоритм Дейкстра/ ошибка - Free Pascal

Формулировка задачи:

Не проходит некоторые тесты в задаче, где нужно найти кратчайший путь от 1-ой вершины неориентированного графа в n-ую. В чём же тут ошибка?

var max,gr,x,y,z,j,i,n,m:longint;
a:array[1..1000,1..1000] of longint;
d,v:array[1..1000] of longint;
BEGIN
readln(n,m);
for i:=1 to m do begin
readln(x,y,z);
if a[x,y]=0 then a[x,y]:=z else if z<a[x,y] then a[x,y]:=z;
if a[y,x]=0 then a[y,x]:=z else if z<a[y,x] then a[y,x]:=z;
end;
i:=1;
while gr<n do begin
for j:=1 to n do
if (d[j]=0) and (v[j]=0) and(a[i,j]>0) then d[j]:=d[i]+a[i,j] else if (d[i]+a[i,j]<d[j]) and (v[j]=0) and (a[i,j]>0) then d[j]:=a[i,j]+d[i];
inc(v[i]);
inc(gr);
max:=maxlongint;
for j:=1 to n do
if (d[j]<=max) and (v[j]=0) then begin max:=d[j]; i:=j; end;
end;
for j:=1 to n do
writeln(d[n]);
end.

Решение задачи: «Алгоритм Дейкстра/ ошибка»

Листинг программы

{
V - множество вершин графа (vertex)
E - множество рёбер графа
w[i,j] - вес (длина) ребра ij
a - вершина, расстояния от которой ищутся
U - множество посещённых вершин (used)
d[u] - по окончании работы алгоритма равно
       длине кратчайшего пути из a до вершины u (distance)
p[u] - по окончании работы алгоритма содержит кратчайший путь из a в u
       (предшествующий u элемент, previous)
}
program Dijkstra;
 
const
  INFINITY  = MaxInt;
  UNDEFINED = -1;
 
const
  Nmax = 6;
type
  TMatrix = array[0..Nmax - 1, 0..Nmax - 1] of integer;
  TVertexList = array[0..Nmax - 1] of integer;
  TDistance = array[0..Nmax - 1] of integer;
  TUsed = array[0..Nmax - 1] of boolean;
 
  function MinOf(const a: TDistance; const m: TUsed): integer;
  var
    i: integer;
    Imin: integer;
    Min: integer;
  begin
    i := low(a);
    while i <= high(a) do
    begin
      if not m[i] then
      begin
        Imin := i;
        Min  := a[i];
        break;
      end;
      inc(i);
    end;
    for i := Imin + 1 to high(a) do
      if (Min > a[i]) and not m[i] then
      begin
        Imin := i;
        Min  := a[i];
      end;
    MinOf := Imin;
  end;
 
  procedure DijkstrasAlgorithm(const W: TMatrix; a: integer;
  var D: TDistance; var P: TVertexList);
  var
    v: integer;
    U: TUsed;
    i, j: integer;
  begin
    {initialization    
      d[a]:=0; p[a]:=0;
      d[v]:=INFINITY; p[v]:=UNDEFINED; для всех вершин отличных от a
    }
    for v := low(D) to high(D) do
    begin
      if v = a then
      begin
        D[v] := 0;
        P[v] := UNDEFINED;
      end
      else
      begin
        D[v] := INFINITY;
        P[v] := UNDEFINED;
      end;
      U[v] := False;
    end;
    {основной цикл}
    for i := low(D) to high(D) do {пока есть нерассмотренные вершины}
    begin
      v := MinOf(D, U); {берём непосещённую вершину с минимальным d[v]}
      U[v] := True;     {отмечаем её как посещённую}
      for j := low(D) to high(D) do
        if W[v, j] <> INFINITY then
          if D[j] > D[v] + W[v, j] then
          begin
            D[j] := D[v] + W[v, j];
            P[j] := v;
          end;
    end;
  end;
 
  procedure ShowPath(A, B: integer; const P: TVertexList; const D: TDistance);
  var
    Q: TVertexList;
    Len: integer;
    v: integer;
  begin
    Len := 0;
    if D[B] = INFINITY then
      writeln('There is not exist path from ', A, ' to ', B, '.')
    else
    begin
      v := B;
      repeat
        Q[Len] := v;
        Inc(Len);
        v := P[v];
      until v=UNDEFINED;
      write('A path from ', A, ' to ', B, ' is <');
      for v := Len - 1 downto 0 do
        Write(Q[v]: 4);
      writeln('>.');
    end;
  end;
 
var
  W: TMatrix =
  (
    (00, 07, 09, 00, 00, 14),
    (07, 00, 10, 15, 00, 00),
    (09, 10, 00, 11, 00, 02),
    (00, 15, 11, 00, 06, 00),
    (00, 00, 00, 06, 00, 09),
    (14, 00, 02, 00, 09, 00)
  );
var
  i, j: integer;
  P: TVertexList;
  D: TDistance;
  A, B: integer;
begin
  {для упрощения ввода вместо INFINITY в матрице весов W я использовал нули
   Поэтому нужно удалить нули из матрицы весов, заменив их на бесконечность}
  for i := 0 to Nmax - 1 do
    for j := 0 to Nmax - 1 do
      if (i <> j) and (W[i, j] = 0) then
        W[i, j] := INFINITY;
  {Ввод начальной и конечной точек маршрута}
  A := 0;
  B := 4;
  {Обработка графа по алгоритму Дейкстры}
  DijkstrasAlgorithm(W, A, D, P);
  {контрольный вывод значений результирующих массивов}
  write('Distance: ');
  for i := low(D) to high(D) do
    Write(D[i]: 4);
  writeln;
  write('Previous: ');
  for i := low(P) to high(P) do
    Write(P[i]: 4);
  writeln;
  {вывод вершин по кратчайшему пути из A в B}
  ShowPath(A, B, P, D);
end.

Объяснение кода листинга программы

{ V - множество вершин графа (vertex) E - множество рёбер графа w[i,j] - вес (длина) ребра ij a - вершина, расстояния от которой ищутся U - множество посещённых вершин (used) d[u] - по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u (distance) p[u] - по окончании работы алгоритма содержит кратчайший путь из a в u (предшествующий u элемент, previous) } В данном коде реализован алгоритм Дейкстры для поиска кратчайшего пути между двумя вершинами графа. Алгоритм работает следующим образом:

Инициализация: - Значения d[a] и p[a] устанавливаются равными 0, что означает, что начальная вершина уже достигнута и является конечной точкой кратчайшего пути. - Для всех вершин, не равных a, значения d[v] устанавливаются равными INFINITY, что означает, что из этих вершин путь не найден. Значения p[v] устанавливаются равными UNDEFINED, что означает, что предшествующая вершина для этих вершин не найдена.
Основной цикл: - На каждой итерации алгоритма выбирается вершина v с минимальным значением d[v]. - Вершина v помечается как посещённая (U[v] := True). - Для каждой вершины j, смежной с v, проверяется, если d[j] больше d[v] + w[v, j], то обновляются значения d[j] и p[j] с учётом нового пути через v.
Вывод: - Выводятся значения d[u] для всех вершин графа. - Выводится путь из начальной вершины a в конечную вершину B. В данном коде используются следующие константы:
- INFINITY - максимальное значение расстояния в графе.
- UNDEFINED - значение, которое получает переменная, если для вершины не найден путь.
- Nmax - количество вершин в графе. В данном коде определены следующие типы и переменные:
- TMatrix - массив, представляющий собой взвешенный граф.
- TVertexList - массив, содержащий номера вершин графа.
- TDistance - массив, содержащий значения расстояний от начальной вершины до всех остальных вершин графа.
- TUsed - массив, содержащий логические значения, указывающие, была ли вершина посещена во время выполнения алгоритма.
- MinOf - функция, которая находит вершину с минимальным значением d[v] среди не посещённых вершин.
- DijkstrasAlgorithm - процедура, которая реализует алгоритм Дейкстры для поиска кратчайшего пути от начальной вершины до всех остальных вершин графа.
- ShowPath - процедура, которая выводит путь из начальной вершины в конечную вершину. В данном коде используются следующие значения:
- A и B - начальная и конечная вершины соответственно.
- W - матрица весов ребер графа.
- P - массив, содержащий предшествующие вершины для каждой вершины графа.
- D - массив, содержащий значения расстояний от начальной вершины до всех остальных вершин графа. В данном коде выполняются следующие действия:
- Инициализация переменных d[a] и p[a].
- Инициализация массива U[v] для всех вершин графа.
- Выполнение алгоритма Дейкстры для поиска кратчайшего пути от начальной вершины до всех остальных вершин графа.
- Вывод значений d[u] для всех вершин графа.
- Вывод пути из начальной вершины в конечную вершину.