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

Узнай цену своей работы

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

Не проходит некоторые тесты в задаче, где нужно найти кратчайший путь от 1-ой вершины неориентированного графа в n-ую. В чём же тут ошибка?
Листинг программы
  1. var max,gr,x,y,z,j,i,n,m:longint;
  2. a:array[1..1000,1..1000] of longint;
  3. d,v:array[1..1000] of longint;
  4. BEGIN
  5. readln(n,m);
  6. for i:=1 to m do begin
  7. readln(x,y,z);
  8. if a[x,y]=0 then a[x,y]:=z else if z<a[x,y] then a[x,y]:=z;
  9. if a[y,x]=0 then a[y,x]:=z else if z<a[y,x] then a[y,x]:=z;
  10. end;
  11. i:=1;
  12. while gr<n do begin
  13. for j:=1 to n do
  14. 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];
  15. inc(v[i]);
  16. inc(gr);
  17. max:=maxlongint;
  18. for j:=1 to n do
  19. if (d[j]<=max) and (v[j]=0) then begin max:=d[j]; i:=j; end;
  20. end;
  21. for j:=1 to n do
  22. writeln(d[n]);
  23. end.

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

textual
Листинг программы
  1. {
  2. V - множество вершин графа (vertex)
  3. E - множество рёбер графа
  4. w[i,j] - вес (длина) ребра ij
  5. a - вершина, расстояния от которой ищутся
  6. U - множество посещённых вершин (used)
  7. d[u] - по окончании работы алгоритма равно
  8.        длине кратчайшего пути из a до вершины u (distance)
  9. p[u] - по окончании работы алгоритма содержит кратчайший путь из a в u
  10.        (предшествующий u элемент, previous)
  11. }
  12. program Dijkstra;
  13.  
  14. const
  15.   INFINITY  = MaxInt;
  16.   UNDEFINED = -1;
  17.  
  18. const
  19.   Nmax = 6;
  20. type
  21.   TMatrix = array[0..Nmax - 1, 0..Nmax - 1] of integer;
  22.   TVertexList = array[0..Nmax - 1] of integer;
  23.   TDistance = array[0..Nmax - 1] of integer;
  24.   TUsed = array[0..Nmax - 1] of boolean;
  25.  
  26.   function MinOf(const a: TDistance; const m: TUsed): integer;
  27.   var
  28.     i: integer;
  29.     Imin: integer;
  30.     Min: integer;
  31.   begin
  32.     i := low(a);
  33.     while i <= high(a) do
  34.     begin
  35.       if not m[i] then
  36.       begin
  37.         Imin := i;
  38.         Min  := a[i];
  39.         break;
  40.       end;
  41.       inc(i);
  42.     end;
  43.     for i := Imin + 1 to high(a) do
  44.       if (Min > a[i]) and not m[i] then
  45.       begin
  46.         Imin := i;
  47.         Min  := a[i];
  48.       end;
  49.     MinOf := Imin;
  50.   end;
  51.  
  52.   procedure DijkstrasAlgorithm(const W: TMatrix; a: integer;
  53.   var D: TDistance; var P: TVertexList);
  54.   var
  55.     v: integer;
  56.     U: TUsed;
  57.     i, j: integer;
  58.   begin
  59.     {initialization    
  60.       d[a]:=0; p[a]:=0;
  61.       d[v]:=INFINITY; p[v]:=UNDEFINED; для всех вершин отличных от a
  62.     }
  63.     for v := low(D) to high(D) do
  64.     begin
  65.       if v = a then
  66.       begin
  67.         D[v] := 0;
  68.         P[v] := UNDEFINED;
  69.       end
  70.       else
  71.       begin
  72.         D[v] := INFINITY;
  73.         P[v] := UNDEFINED;
  74.       end;
  75.       U[v] := False;
  76.     end;
  77.     {основной цикл}
  78.     for i := low(D) to high(D) do {пока есть нерассмотренные вершины}
  79.     begin
  80.       v := MinOf(D, U); {берём непосещённую вершину с минимальным d[v]}
  81.       U[v] := True;     {отмечаем её как посещённую}
  82.       for j := low(D) to high(D) do
  83.         if W[v, j] <> INFINITY then
  84.           if D[j] > D[v] + W[v, j] then
  85.           begin
  86.             D[j] := D[v] + W[v, j];
  87.             P[j] := v;
  88.           end;
  89.     end;
  90.   end;
  91.  
  92.   procedure ShowPath(A, B: integer; const P: TVertexList; const D: TDistance);
  93.   var
  94.     Q: TVertexList;
  95.     Len: integer;
  96.     v: integer;
  97.   begin
  98.     Len := 0;
  99.     if D[B] = INFINITY then
  100.       writeln('There is not exist path from ', A, ' to ', B, '.')
  101.     else
  102.     begin
  103.       v := B;
  104.       repeat
  105.         Q[Len] := v;
  106.         Inc(Len);
  107.         v := P[v];
  108.       until v=UNDEFINED;
  109.       write('A path from ', A, ' to ', B, ' is <');
  110.       for v := Len - 1 downto 0 do
  111.         Write(Q[v]: 4);
  112.       writeln('>.');
  113.     end;
  114.   end;
  115.  
  116. var
  117.   W: TMatrix =
  118.   (
  119.     (00, 07, 09, 00, 00, 14),
  120.     (07, 00, 10, 15, 00, 00),
  121.     (09, 10, 00, 11, 00, 02),
  122.     (00, 15, 11, 00, 06, 00),
  123.     (00, 00, 00, 06, 00, 09),
  124.     (14, 00, 02, 00, 09, 00)
  125.   );
  126. var
  127.   i, j: integer;
  128.   P: TVertexList;
  129.   D: TDistance;
  130.   A, B: integer;
  131. begin
  132.   {для упрощения ввода вместо INFINITY в матрице весов W я использовал нули
  133.    Поэтому нужно удалить нули из матрицы весов, заменив их на бесконечность}
  134.   for i := 0 to Nmax - 1 do
  135.     for j := 0 to Nmax - 1 do
  136.       if (i <> j) and (W[i, j] = 0) then
  137.         W[i, j] := INFINITY;
  138.   {Ввод начальной и конечной точек маршрута}
  139.   A := 0;
  140.   B := 4;
  141.   {Обработка графа по алгоритму Дейкстры}
  142.   DijkstrasAlgorithm(W, A, D, P);
  143.   {контрольный вывод значений результирующих массивов}
  144.   write('Distance: ');
  145.   for i := low(D) to high(D) do
  146.     Write(D[i]: 4);
  147.   writeln;
  148.   write('Previous: ');
  149.   for i := low(P) to high(P) do
  150.     Write(P[i]: 4);
  151.   writeln;
  152.   {вывод вершин по кратчайшему пути из A в B}
  153.   ShowPath(A, B, P, D);
  154. end.

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

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

  1. Инициализация:   - Значения d[a] и p[a] устанавливаются равными 0, что означает, что начальная вершина уже достигнута и является конечной точкой кратчайшего пути.   - Для всех вершин, не равных a, значения d[v] устанавливаются равными INFINITY, что означает, что из этих вершин путь не найден. Значения p[v] устанавливаются равными UNDEFINED, что означает, что предшествующая вершина для этих вершин не найдена.
  2. Основной цикл:   - На каждой итерации алгоритма выбирается вершина v с минимальным значением d[v].   - Вершина v помечается как посещённая (U[v] := True).   - Для каждой вершины j, смежной с v, проверяется, если d[j] больше d[v] + w[v, j], то обновляются значения d[j] и p[j] с учётом нового пути через v.
  3. Вывод:   - Выводятся значения 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] для всех вершин графа.
    • Вывод пути из начальной вершины в конечную вершину.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.667 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы