Алгоритмы поиска в ширину и в глубину в графе

1) Дано N городов, некоторые из них  соединены двусторонними дорогами. Проезда по каждой дороге имеет  свою стоимость. Необходимо составить  программу, которая по заданной  таблице истинности находит путь от города S1 до города S2, суммарная стоимость которая будет минимальна.

Формат  входных данных: на вход подаётся файл, содержащий в первой строке N. S1 и S2. (1<=N<=50, 1<=S1<=N, 1<=S2<=N). Затем в  следующих N строках идут числа, описывающие  очередную строку матрицы смежности.

Формат  выходных данных: на экран вывести  города, которые следуют в искомом  пути.

Пример:

5 2 4

0 7 0 8 12

7 0 1 0 0

0 1 0 4 2

8 0 4 0 1

12 0 2 1 0

Ответ:

2->3->5->4

Решение: наиболее удачным и быстродейственным  способом нахождения пути от одного пункта к другому является метод Дейкстры, которая ищет минимальные расстояния от какой-то заданной точки до всех остальных. В алгоритме заведём массив предков P(N), который будет содержать минимальный путь, где P[I] - точка, от которой пришли в I по найденному минимальному пути. P[S] будет равно нулю, если S - корневая вершина (от которой и ищем пути).

const MaxN = 50;

INF = 1000000000; //"бесконечность"

 

type Matrix = array[1..MaxN,1..MaxN] of longint; //тип матрицы  смежности. M[i,j] = true, если существует ребро, идущее от вершины i к j

 

var

A : Matrix; N, S1, S2: integer;

input: text;

 

procedure Input_Table(var A : Matrix; N : longint; var T : Text); //процедура ввода матрицы смежности A(N, N) из текстового файла T

var i, j : longint;

begin

    for i := 1 to N do

    begin

        for j := 1 to N do

        begin

            read(T, A[i, j]);

            if (a[i,j] = 0) and (i <> j) then a[i,j] := INF; //вершины, которые не связаны ребром, будем обзначать "бесконечностью" ввиду ограничения на вес рёбер

        end;

        readln(T);

    end;

end;

 

procedure Deikstr(s, s1 : integer); //s, s1 - искомые вершины (необходимо найти путь от s до s1)

var i, j, v, min, z : longint;

st, c : string;

visited : array[1..MaxN]of boolean; //массив посещённости вершин

D : array[1..MaxN] of longint; //массив кратчайших расстояний

P : array[1..MaxN] of integer; //массив предков, который  поможет определить маршрут. p[i] будет  содержать предпоследнюю вершину кратчайшего маршрута от s до i

 

begin

 

    for i := 1 to N do

    begin

        p[i] := s;

        visited[i] := FALSE;

    end;

    visited[s] := TRUE; //вершина S посещена

 

    for i := 1 to N do D[i] := A[s, i]; //изначальный массив расстояний

    D[s] := 0;

 

    p[s] := 0; //

 

    for i := 1 to N-1 do //на каждом шаге находим минимальное решение и пытаемся его улучшить

    begin

        min := INF;

        for j := 1 to N do if (not visited[j]) and (D[j] < min) then

        begin

            min := D[j]; //минимальное расстояние

            v := j; //найденная вершина

        end;

        for j := 1 to N do if (D[j] > D[v] + A[v, j]) and (D[v] < INF) and (A[v, j] < INF) then

        begin

            D[j] := D[v] + A[v, j]; //пытаемся улучшить  решение. Если в ней расстояние  больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его.

            p[j] := v;

        end;

        s := v; //новая текущая вершина

        visited[v] := TRUE; //и она отмечается  посещенной

    end;

 

    st := ''; //осталось преобразовать в  формат вывода (мы проидёмся по всем вершинам кратчайшего пути от s до s1, но только в обратном порядке)

    z := p[s1]; //пока есть корневая вершина

    while z <> 0 do

    begin

        str(z,c);

        st := c + '->' + st; //заносим в маршрут

        z := p[z]; //переходим к следующей вершине

    end;

    str(s1,c); //в маршрут записываем начальную  вершину

    st := st + c;

    writeln(st);

end;

 

BEGIN

    assign(input,'input.txt');

    reset(input);

    readln(input, N, S1, S2);

    Input_Table(A, N, input);

    close(input);

    Deikstr(S1, S2);

END.