Найти кратчайший путь между двумя заданными городами - Pascal

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

Дана плоская страна и в ней n городов. Предположим, что в этой стране есть дорожная сеть. Найти кратчайший путь между двумя заданными городами. должна находить кратчайшие расстояния и выводить маршрут (последовательность прохождения городов). Как дописать программу, чтобы она выводила маршрут?

program Project64;
uses
  SysUtils,
  windows;
const
n = 8;
inf = 1000;
var
f: text;
D: array[1..n, 1..n] of integer;
i, j, k, p,min:integer;         //k-начальная вершина   p-счетчик
A,B,C: array[1..n] of integer;
begin
  SetConsoleOutputCP(1251);
  SetConsoleCP(1251);
  Assign(f, 'Алгоритм.txt');
  Reset(f);
    for i:=1 to n do
      for j:=1 to n do
      begin
        read(f, d[i,j]);
        if d[i,j]=-1 then d[i,j]:=inf;  //считали из файла матрицу
      end;
  Close(f);
    for i:=1 to n do
    begin
      for j:=1 to n do
        if d[i,j]=inf then write('-':5)
        else  write(d[i,j]:5);     //напечатали
        writeln;
    end;
  writeln('Введите начальную вершину');
  readln(k);
   for i:=1 to n do
     begin              //заполнили массив
      A[i]:=0;
      b[i]:=D[k,i];
      C[i]:=k;
     end;
   A[k]:=1;
  for p:=1 to n-1 do
    begin
    min:=inf;    //пошёл сам алгоритм
      for i:=1 to n do
        begin
          if (A[i]=0) and (B[i]<min) then
            begin
              min:=B[i];
              j:=i;
            end;
          end;
            A[j]:=1;
          for i:=1 to n do
              if B[i]>B[j]+D[i,j]  then
              begin
                B[i]:=B[j]+D[i,j];
                C[i]:=j;
              end;
        end;
   for i:=1 to n do
   begin
     write(i:6);
     writeln(B[i]:5);
   end;
  readln;
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.

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

В данном коде реализован алгоритм Дейкстры для поиска кратчайшего пути между двумя заданными вершинами в графе.

Объявлены типы данных и константы:
- TMatrix - массив размером Nmax x Nmax, представляющий собой взвешенный граф. Вес ребра ij хранится в элементе w[i,j].
- TVertexList - массив размером Nmax, содержащий вершины графа.
- TDistance - массив размером Nmax, в котором при завершении работы алгоритма будет содержаться длина кратчайшего пути от начальной вершины до каждой вершины графа.
- TUsed - массив размером Nmax, который используется для отметки посещенных вершин.
- INFINITY - максимальное значение расстояния в графе.
- UNDEFINED - значение, обозначающее, что вершина не была посещена.
- Nmax - количество вершин в графе.
Задана матрица весов графа W.
Заданы начальная и конечная вершины маршрута (A и B).
Выполняется функция MinOf, которая находит вершину с минимальным значением расстояния в непосещенных вершинах.
Выполняется основная функция DijkstrasAlgorithm, которая реализует алгоритм Дейкстры. В ней происходит итеративное нахождение кратчайшего пути от начальной вершины до каждой вершины графа. Функция использует вспомогательные переменные d[v] и p[v] для хранения текущего расстояния до вершины v и предыдущей вершины в пути.
Выполняется функция ShowPath, которая выводит путь от начальной до конечной вершины.
Запускается основной код программы:
- Выполняется инициализация массивов d и p.
- Выполняется цикл, в котором находятся вершины с минимальным значением расстояния и обновляется расстояние до соседних вершин.
- Выводятся значения массивов d и p.
- Выполняется вызов функции ShowPath для вывода пути от начальной до конечной вершины.