Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
mybook11.05.12.doc
Скачиваний:
15
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей

Известна стоимость проезда из каждого города в каждый. Hайти наименьшую стоимость проезда из города 1 до всех остальных и путь из одной вершины в другую за время O(n3).

program floid;

const k=10;

var a,d,m:array[1..k,1..k] of integer;

i,j,t,n,nach,kon:integer;

procedure init; инициализация исходных данных

begin

assign(input,'input.txt');

reset(input);

read(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

read(nach,kon);

for i:=1 to n do

for j:=1 to n do

m[i,j]:=i;

end;

procedure distanse; построение матрицы путей

var i,j,t:integer;

begin

for i:=1 to n do

for j:=1 to n do

d[i,j]:=a[i,j];

for i:=1 to n do d[i,i]:=0;

for t:=1 to n do

for i:=1 to n do

for j:=1 to n do

if d[i,j]>d[i,t]+d[t,j] если путь из i в j через вершину t короче

then

begin

d[i,j]:=d[i,t]+d[t,j]; то изменяем d[i,j]

m[i,j]:=m[t,j]; и заносим вершину t в путь

end;

end;

procedure allway(i,j:integer); рекурсивная процедура вывода пути i из в j

begin

if m[i,j]=i then

if i=j then write(i) else write (i,'-',j,' ')

else

begin

allway(i,m[i,j]); allway(m[i,j],j);

end;

end;

procedure out; вывод матрицы кратчайших расстояний

begin

assign(output,'output.txt');

rewrite(output);

for i:=1 to n do

begin

writeln;

for j:=1 to n do

write(d[i,j],' ');

end;

writeln;

end;

begin

init;

distanse;

out;

allway(nach,kon);

end.

Пример файла Input.txt

4 размеры матрицы

0 1 2 1 сама матрица

2 0 7 32767

6 5 0 2

1 32767 4 0

3 2 начальная и конечная вершины

Пример файла Output.txt

матрица кратчайших расстояний

0 1 2 1

2 0 4 3

3 4 0 2

1 2 3 0

3-4 4-1 1-2 путь из 3 во 2

Время работы алгоритма: O(n3)

графызадачи

Алгоритм Форда-Беллмана нахождения длин кратчайших путей из первой вершины во все

Алгоритм работает и в случае, когда в графе есть и отрицательные веса ребер.

Обозначим через МинСт(1,s,к) наименьшую длину пути из 1 в s такую, что путь содержит не более чем k ребер. Тогда выполняется такое соотношение:

МинСт (1,s,k+1) = наименьшему из чисел МинСт(1,s,k) и МинСт(1,i,k) + a[i][s] (i=1..n). Как отмечалось выше, искомым ответом является МинСт(1,i,n) для всех i=1..n.

Program bellman;

const nmax=100;

besk=maxint div 2;

var k,i,j,s,n:integer;

a:array[1..nmax,1..nmax] of integer;

x:array[1..nmax] of integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

for i:=1 to n do

for j:=1 to n do

begin

read(a[i,j]);

if a[i,j]=0 then a[i,j]:=besk;

end;

k:= 1; ребро одно

for i := 1 to n do копируем первую строку матрицы

смежности в массив x

x[i] := a[1,i];

while k <> n do begin пока в рассматриваемом пути не все ребра

for j := 1 to n do перебираем вершины, в которые идем

begin

for i := 1 to n do перебираем промежуточные вершины

begin

if x[j] > x[i]+a[i,j] then если длина пути из 1 в вершину j через

begin вершину i короче, чем из 1 в j

x[j] := x[i]+a[i,j]; запоминаем ее

end;

end;

end;

k := k + 1; добавляем еще одно ребро

end;

end.

графызадачи

Это - алгоритм динамического программирования, или алгоритм Форда - Беллмана. Алгоритм может быть улучшен в двух отношениях: можно за то же время O(n3) найти наименьшую стоимость проезда из i в j для всех пар i,j (а не только с i=1), а можно сократить время работы до O(n2). Правда, в последнем случае нам потребуется, чтобы все веса a[i,j] были неотрицательны.

Алгоритм Краскала . Построение минимального остовного дерева.

Алгоритм получения минимального каркаса будет следующим:

1. Упорядочить ребра графа в порядке неубывания их весов.

2. Начав с первого ребра в этом перечне, добавлять ребра в новый граф , соблюдая условие: добавление не должно приводить к появлению цикла.

3. Повторять шаг 2 до тех пор, пока число ребер в новом графе не станет равным N-1. Получившееся дерево является каркасом минимального веса

На рисунке приведен пример получения минимального остовного дерева.

Program kraskal;

const nmax=10;

var v:array[1..3,1..nmax*nmax div 2] of integer; v[1,i] -номер 1 вершины ребра

c:array[1..nmax] of integer; v[2,i]-номер 2 вершины ребра

a:array[1..nmax,1..nmax] of integer; v[3,i]-вес ребра

i,j,n,t:integer;

Procedure Init;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

for i:=1 to n do считывание матрицы смежности

for j:=1 to n do

read(a[i,j]);

end;

Procedure Solve;

begin

t:=1;

for i:=1 to n do заполнение массива v

for j:=i+1 to n do

if a[i,j]<>0

then

begin

v[1,t]:=i;

v[2,t]:=j;

v[3,t]:=a[i,j];

inc(t);

end;

for i:=1 to n*n div 2-1 do упорядочение массива v по неубыванию

for j:=i+1 to n*n div 2 do по весу ребер

if v[3,i]>v[3,j] then

begin

t:=v[3,i];

v[3,i]:=v[3,j];

v[3,j]:=t;

t:=v[1,i];

v[1,i]:=v[1,j];

v[1,j]:=t;

t:=v[2,i];

v[2,i]:=v[2,j];

v[2,j]:=t;

end;

for i:=1 to n do c[i]:=i; заполнение массива цветов

t:=0; счетчик количества ребер в минимальном

каркасе

for j:=1 to n*n div 2 do проверка всех ребер

begin

if t=n-1 then halt(0); если все ребра минимального каркаса

получены, то конец

if c[v[1,j]]<>c[v[2,j]] если цвета концов ребра различны

then

begin

writeln(v[1,j],' ',v[2,j]); выводим ребро

c[v[2,j]]:= c[v[1,j]]; меняем цвет конца ребра в цвет начала

inc(t); считаем ребро

end;

end;

close(output);

end;

Begin Init; Solve;end.

графызадачи

Нахождение Эйлерова цикла

Опр. Эйлеровым циклом называется цикл, который проходит по каждому ребру один раз.

Для выяснения того факта есть ли в данном графе Эйлеров цикл будем использовать следующую теорему.

Теорема: Связанный неориентированный граф содержит Эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю.

Граф, содержащий Эйлеров цикл можно нарисовать на бумаге, не отрывая от нее карандаш. Для нахождения Эйлерова цикла используется обход в глубину, при этом ребра удаляются, для того, чтобы не проходить по ребру более одного раза. Порядок просмотра вершин запоминается. При обнаружении вершины, из которой не выходят ребра, ее номер записывается в стек, и просмотр продолжается от предыдущей вершины. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, так как четность вершин (количество выходящих ребер) при этом не изменится. Процесс продолжается до тех пор пока есть ребра. В стеке будут записаны номера вершин графа в порядке, соответствующем Эйлерову циклу.

Program Eiler_Cycle;

const

nmax=100;

var

a:array[1..nmax,1..nmax]of integer; матрица смежности графа

d:array[1..nmax]of integer; содержит вершины входящие в

Эйлеров цикл

n,kol,i:integer;

Procedure Init;

var i,j:integer;

Begin

assign(input,'input.txt');reset(input);

read(n);

for i:=1 to n do for j:=1 to n do read(a[i,j]);

close(input);

fillchar(d,sizeof(d),0);kol:=0

End;

Procedure Out;

var i:integer;

Begin

assign(output,'output.txt');rewrite(output);

for i:=1 to kol do write(d[i],' ');

close(output)

End;

Procedure Rec(v:integer); рекурсивная процедура поиска Эйлерова

цикла

var i:integer;

Begin

for i:=1 to n do ищем вершину связанную с вершиной v

if a[v,i]<>0 then если такую нашли

begin

a[v,i]:=0;a[i,v]:=0; удаляем ребро

Rec(i); запускаем рекурсию от найденной вершины

end;

inc(kol); на подъеме из стека вершину считаем

d[kol]:=v и заносим в Эйлеров цикл

End;

Begin

Init;

Solve(1);

Out

End.

графызадачи

Нахождение Гамильтонова цикла в графе методом backtreckinga

Опр. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом.

Алгоритм нахождения гамильтонова цикла следующий:

  1. Начиная с вершины с номером 1 будем продвигаться впнред по графу, включая очередное ребро в гамильтонов цикл.

  2. При найденных первых К компонентах решения рассматриваем ребра, которые выходят из последней вершины. Если находим ребро, которое ведет в непосещенную ранее вершину, добавляем новую вершину в цикл и она становится просмотренной.

  3. При отсутствии такой вершины возвращаемся к предыдущей и ищем другие вершины, смежные с ней.

Program gamilton;

const maxn=100;

var

a:array[1..maxn,1..maxn] of integer; матрица смежности

st:array[1..maxn] of integer; массив для хранения порядка

просмотра вершин

used:array[1..maxn] of boolean; массив признаков использована вершина или нет

n:integer;

procedure init;

var i,j:byte;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

close(input);

fillchar(used,sizeof(used),false);

fillchar(st,sizeof(st),0);

end;

procedure out;

var i:integer;

begin

for i:=1 to n do write(st[i],' ');write('1');

close(output);

end;

procedure rec(k:integer); к- номер просматриваемой вершины

var v,i:integer;

begin

v:=st[k-1]; номер последней просмотренной вершины

for i:=1 to n do цикл по всем вершинам

if a[v,i]<>0 then если вершины v и i связаны

begin

if (k=n+1)and(i=1) если дошли до последней вершины

then out выводим путь

else иначе

if not used[i] если вершина i не использована

then тогда

begin

st[k]:=i; заносим ее в путь

used[i]:=true; отмечаем как пройденную

rec(k+1); переходим к следующей

used[i]:=false; возвращаемся на один шаг назад, снимаем

отметку

end;

end;

end;

procedure solve;

begin

st[1]:=1; заносим первую вершину в путь

used[1]:=true; отмечаем как пройденную

rec(2); запускаем рекурсию со второй вершины

end;

begin init; solve; out; end.

графызадачи

Максимальное паросочетание

Пусть есть граф G=(V, E). Подмножество его ребер, такое что никакие два ребра из этого подмножества не инцидентны какой-либо одной вершине из V, называется паросочетанием. Задача определения максимального подмножества таких ребер называется задачей нахождения максимального паросочетания. Полным паросочетанием называется паросочетание, в котором участвуют (в качестве концов ребер) все вершины графа. Очевидно, что любое полное паросочетание является также максимальным паросочетанием.

Данный алгоритм поиска максимального паросочетания использует метод, известный как "чередующиеся цепи". Пусть M — паросочетание в графе G. Вершину v будем называть парной, если она является концом одного из ребер паросочетания M. Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в множество M, называется чередующейся (аргументальной) цепью относительно M. Очевидно, что чередующаяся цепь должна быть нечетной длины, начинаться и заканчиваться ребрами, не входящими в множество M. Также ясно, что имея чередующуюся цепь P, мы можем увеличить паросочетание M, удалив из него те ребра, которые входят в цепь P, и вместо удаленных ребер добавить ребра из цепи P, которые первоначально не входили в паросочетание M. Это новое паросочетание можно определить как M^P, где ^ обозначает симметрическую разность множеств M и P, т. е в новое множество паросочетаний войдут те ребра, которые входят или в множество M, или в множество P, но не в оба сразу.

Паросочетание M будет максимальным тогда и только тогда, когда не будет существовать чередующейся цепи относительно M.

Теперь можно описать алгоритм нахождения максимального паросочетания M для графа G=(V, E).

  1. Сначала положим M=0

  2. Далее ищем чередующуюся цепь P относительно M, и множество M заменяется на множество M^P

  3. Шаг 2 выполняется до тех пор, пока существуют чередующиеся цепи относительно M Если таких цепей нет, то M — максимальное паросочетание.

графызадачи

Поиск компонент связности

Пусть G — граф. Разобъем множество его вершин на компоненты связности по следующему принципу: две вершины лежат в одной компоненте связности, когда есть путь из одной вершины в другую.

Если выполнить DFS(a) при условии, что все вершины изначально не помечены, то алгоритм посетит все вершины, достижимые из a. Поэтому его можно применять для поиска связных компонент. Для этого будем для каждой помеченной вершины хранить номер ее компоненты связности, который будем также называть цветом. Непройденные вершины считаем непокрашенными. Алгоритм работает так:

DFS(a,c)

Покрасить вершину a в цвет c

Для любого ребра (a,b)

Если вершина b не покрашена, то

DFS(b,c)

Нахождение сомпоненты

Изначально все вершины не покрашены

c := 0

Для любой вершины a,

Если a не покрашена, то

c := c+1

DFS(a,c)

Топологическая сортировка

Пусть задан ориентированный граф G без циклов. Топологической сортировкой в нем называется такое упорядочение его вершин, что для любого ребра (a,b), вершина a расположена раньше вершины b в этом упорядочении. Ясно, что может существовать несколько топологических сортировок нашего графа.

Для того, чтобы найти топологическую сортировку графа, упорядочим вершины в порядке убывания времени выхода, т. е. момента, в который алгоритм поиска в глубину закончил обработку вершины. Это и будет топологической сортировкой.

DFS(a)

Пометить вершину a

Для любого ребра (a,b),

Если вершина b не помечена, то

DFS(b)

Добавить a в начало списка вершин

TOPOLOGICAL_SORT

Изначально список вершин пуст, никакая вершина не помечена

Для любой вершины a,

Если a не помечена, то

DFS(a)

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]