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

жүктеу/скачать 43 Kb.

Дата	04.12.2019
өлшемі	43 Kb.
	#52978

Байланысты:
граф 1

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

BashВыделить код

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

Ответ:

BashВыделить код

1	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;

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.

жүктеу/скачать 43 Kb.

Достарыңызбен бөлісу: