Алгоритм Дейкстра/ ошибка - 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.
Решение задачи: «Алгоритм Дейкстра/ ошибка»
textual
Листинг программы
- {
- 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] для всех вершин графа.
- Вывод пути из начальной вершины в конечную вершину.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д