Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

1. Для каждой вершины u, смежной v, проверяем, отмечена ли она и какова длина пути между u и v. Если меньше, то запоминаем длину пути и текущую вершину u.

2. t= ∞, v=0. Для каждой вершины графа проверяем, отмечена ли она, и меньше ли путь от нее до s, чем t. Если так, то запоминаем её v=u, и её путь t=T[u] .

3. Если v=0, то пути нет, иначе если v=f, то путь найден и конец алгоритма.

4. Помечаем вершину v. Переход в п.1.

4.3 Выбор структур данных

Пусть p – количество вершин. Поскольку граф взвешен, то его представим в форме матрицы длин дуг:

С: array[1..p,1..p].

Используются следующие переменные и массивы:

s, f – вершины, между которыми следует найти кратчайший путь;

u, v – переменные циклов по вершинам;

T: array[1..p] ofreal – вектор, если вершина v лежит на кратчайшем пути от s к t, то T[v] – длина кратчайшего пути от s к v;

H: array[1..p] of 0..p – вектор, H[v] – вершина, непосредственно предшествующая v на кратчайшем пути;

X: array[1..p] of 0..1 – вектор меток вершин.

4.4 Описание схемы алгоритма

Блок-схема данного алгоритма изображена на рис. 4 в Приложении.

В блоке 1 происходит ввод графа в форме матрицы длин дуг, а также номеров вершин s и f. Далее организуется цикл по вершинам графа (блок 2). В нем инициализируются массив кратчайших путей и массив меток (блок 3): поскольку пути не известны, то они инициализируются бесконечностью, а метки – нулем. Далее отмечается вершина s, кратчайший путь от неё до неё же самой равен 0, и ей никто не предшествует; текущей вершиной v становится s (блок 5). Далее организовывается цикл по смежным с текущей вершинам (блок 6). В блоке 7 происходит проверка смежны ли вершины. В блоке 8 сравнивается уже имеющийся путь с путем между u и v. Если текущий меньше, то он и номер вершины запоминаются (блок 9).

В остальных блоках происходит поиск конца кратчайшего пути. Изначально его длина не известна (равна ∞), и вершина, оканчивающая его также не известна (блок 11). В блоке 12 организуется цикл по всем неотмеченным вершинам. В блоке 13 производиться сравнение уже имеющегося кратчайшего пути t с текущим T[u]. Если текущий меньше, то запоминаем его и вершину (блок 14). Далее производится анализ полученного конца пути. Если v=0 (блок 16), то не была найдена вершина конца кратчайшего пути, и, следовательно, нет такого пути (блок 17). Если же v=f (блок 18), то есть конец совпадает с заданной вершиной, то между ними существует кратчайший путь (блок 19). В обоих случаях конец алгоритма.

Если же не достигнута заданная вершина f, то текущая вершина v помечается (блок 20) и переход в блок 6.

Алгоритм работает, пока не будет вершина t либо пока не станет ясно, что пути из s в f нет.

4.5 Контрольный пример решения задачи с помощью алгоритма поиска кратчайшего пути

Пусть задан граф, изображенный на рис. 1. Рассмотрим на этом примере работу алгоритма.

0. for v=1..p

T[v]=∞;

X[v]=0;

H[s]=0;

T[s]=0;

X[s]=1;

v=s;

1. X2 € G(1) →

X[2]=0&(∞>0+4) →

T[2]=T[1]+C[1,2]=4;

H[2]=1;