Алгоритм Дейкстры - Вывести не только вес ребер, но и сам путь - PascalABC.NET

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

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

Необходимо вывести не только вес ребер, но и сам путь, например: 1-3-5. Помогите, пожалуйста.

Решение задачи: «Алгоритм Дейкстры - Вывести не только вес ребер, но и сам путь»

textual
Листинг программы
const
  n = 6;
  inf = 100000;
 
type
  mas1 = array[1..n, 1..n] of integer;
  mas2 = array[1..n] of boolean;
  mas3 = array[1..n] of integer;
 
const
  GM: mas1 = //матрица смежности графа
  (
  (0, 9, 1, 4, 0, 0), //1
   
  (0, 0, 0, 0, 0, 0), //2
   
  (1, 0, 0, 3, 2, 4), //3
   
  (4, 0, 3, 0, 0, 1), //4
   
  (0, 0, 2, 0, 0, 2), //5
   
  (0, 0, 4, 1, 2, 0)  //6
  );
 
procedure Dijkstra(GM: mas1; st: integer);
  var
    count, index, i, u, m, min: integer;
    distance: mas3;//найденные пути
    from: mas3;//из какой вершины пришли
    visited: mas2;//массив посещенных вершин
  procedure printway(k: integer);//вывод кратчайшего пути
  begin
    if (from[k] <> m) and (k <> m) then 
    begin
      printway(from[k]);
      write(' > ');
    end;
    write(k);
  end;
  begin
    m := st;
    for i := 1 to n do
    begin
      distance[i] := inf; 
      visited[i] := false;
    end;
    distance[st] := 0;
    for count := 1 to n - 1 do
    begin
      min := inf;
      for i := 1 to n do
        if (not visited[i]) and (distance[i] <= min) then
        begin
          min := distance[i]; 
          index := i;
        end;
      u := index;
      visited[u] := true;
      for i := 1 to n do
        if (not visited[i]) and (GM[u, i] <> 0) and (distance[u] <> inf) and 
        (distance[u] + GM[u, i] < distance[i]) then
        begin
          distance[i] := distance[u] + GM[u, i];//вычисляется стоимость маршрута 
          from[i] := u
        end;
    end;
    write('Стоимость пути из начальной вершины до остальных:');
    writeln;
    for i := 1 to n do
    begin
      write(m, ' > ', i, ' = ');
      if distance[i] = inf then writeln('маршрут недоступен')
      else 
      begin
        write(distance[i], ' Путь: ', m, ' > ');
        printway(i);
        writeln
      end;
    end;
  end;
 
begin
  dijkstra(gm, 1);
end.

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

  1. В начале определены константы: n = 6 (количество вершин графа), inf = 100000 (бесконечность), GM (матрица смежности графа).
  2. Далее, в процедуре Dijkstra, объявлены вспомогательные переменные: count, index, i, u, m, min.
  3. Также, объявлены две переменные: distance (найденные пути) и from (из какой вершины пришли).
  4. Есть еще одна вспомогательная процедура printway, которая выводит кратчайший путь.
  5. В основной части программы начинается с выбора начальной вершины (m = 1).
  6. Затем, в цикле for, все вершины помечаются как не посещенные и устанавливаются в бесконечность, кроме m, который равен 0.
  7. Цикл while ищет кратчайший путь от m до всех остальных вершин.
  8. На каждой итерации, находится вершина с наименьшим расстоянием (min), и если она не посещена, то происходит поиск пути от нее до других вершин.
  9. Если найденный путь короче, чем текущий, то обновляется текущий путь и запоминается предыдущая вершина.
  10. После окончания цикла, выводится стоимость пути от начальной вершины до остальных вершин.
  11. Для каждой вершины выводится ее номер, путь от начальной вершины до нее и стоимость этого пути.
  12. Если путь недоступен (равен бесконечности), то выводится соответствующее сообщение.
  13. Если путь доступен, то выводится путь и его стоимость.

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

12   голосов , оценка 3.5 из 5
Похожие ответы