Алгоритмы на графах

В результате работы алгоритма получим  длину кратчайшего пути из s в q. Чтобы  найти вершину и ребра, составляющие этот путь, нужно определить массив h[|V|], где h[v] – вершина, предшествующая вершине v на кратчайшем пути, а в  шаге 2 добавить операцию h[u] = v, в случае, когда t (u) > t (v)+a[v][u].

Можно получить кратчайшие пути от s ко всем другим вершинам, изменив условие  остановки. Вычисления заканчиваются, когда все веса становятся постоянными.

В тексте программы веса вершин записываются в массив t [ ]. Для обозначения того, что для вершины v вес t [v] постоянный, вводится массив x[ ]. Равенство x[v]=1 будет означать, что t [v] – постоянный вес.

Вот как выглядит общий алгоритм нахождения минимального расстояния между двумя заданными вершинами в псевдокоде:

1: 

2:Для всех   отличных от a

3:присвоим 

4:Пока 

5:Пусть   — вершина с минимальным d[v]

6:Для всех   таких, что 

7:если d[u] > d[v] + w[vu] то

8:изменим 

9:изменим 

Обозначения:

V — множество вершин графа

E — множество ребер графа

w[ij] — вес (длина) ребра ij

a — вершина, расстояния от которой ищутся

U — множество посещенных вершин

d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u

p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u

 

Доказательство того, что вышеприведенный  алгоритм действительно дает кратчайшие пути.

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин с этими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью по вершинам множества S1. (Так как при каждой итерации во множество S1 включается только одна вершина, то обновление пометки l(xi) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к xi* не проходит целиком по S1 и содержит по крайней мере одну вершину из S2, и пусть xj S2 – первая такая вершина в этом пути. Так как по предположению cij неотрицательны, то часть пути от xj к xi* должна иметь неотрицательный вес   и . Это, однако, противоречит утверждению, что l(xi*) – наименьшая временная пометка, и, следовательно, кратчайший путь к xi* проходит полностью по вершинам множества S1, и поэтому l(xi*) является его длиной.

Так как вначале множество S1 равно (s) при каждой итерации к S1 добавляется xi*, то предположение, что l(xi*) равно длине кратчайшего пути  xi S1, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Если  требуется найти кратчайшие пути между s и всеми другими вершинами  полного связного графа с n вершинами, то в процессе работы алгоритма выполняются  операций сложения и сравнения на шаге 2 и еще   операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще   операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.

Как только длины кратчайших путей от s будут найдены (они будут заключительными  значениями пометок вершин), сами пути можно получить при помощи рекурсивной  процедуры с использованием соотношения (*). Так как вершина xi' непосредственно предшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну из оставшихся вершин, для которой

' ' . (*)

Если  кратчайший путь от s до любой вершины  xi является единственным, то дуги (xi', xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине xi' соотношение (*) будет выполняться для более чем одной вершины xi. В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и xi), либо таким, что рассматриваются все дуги (xi', xi), входящие в какой-либо из кратчайших путей и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s или кратко – s-базой.

 

3. Структура программы

 

Проект  выполнен в среде разработки C++ Builder 2009 и называется KursGraths. Он содержит одну (главную) форму с расположенными на ней обработчиками событий (controls). Описание основных пользовательских типов и переменных, используемых в каждом конкретном обработчике вынесены в его начало. В таблице, приведенной ниже, описаны основные функции каждого из обработчиков событий главного модуля.

Имя обработчика	Название контрола	Функции
TForm3	Курсовая работа: Графы. Выполнил Чернов Денис гр.230791	Здесь описано окно программы, которое видит пользователь сразу  после ее запуска. Размещены процедуры импорта графа, вывода графа на экран, кнопки определения свойств графа, кнопки очистки полей изображений, печати заданного графа, кнопка вызова справки.
TButton1	Печать	Отправка графа на печать принтеру (Виртуальному или физическому)
TButton2	Открыть	Импорт матрицы смежности  из файла
TButton3	Справка	Вызов файла help.txt
TButton4	Минимальный остов	Процедура построения минимального остовного дерева для импортированого графа
TButton5	Clear All	Очищает первую картинку с графом
TButton6	Clear All	Очищает вторую картинку с графом
TButton7	Кратчайший путь	Процедура нахождения минимального расстояния между двумя задаными вершинами в импортированом графе
Edit4	Начальная вершина	Поле ввода начальной  вершины
Edit5	Конечная вершина	Поле ввода конечной вершины
Image1	Граф1	Форма для рисования графа (для определения кратчайшего  пути)
Image2	Граф2	Форма для рисования графа (для определения минимального остовного дерева)

 

В программе также используется подключаемая библиотека KursGrath.h, содержащая прототипы функций используемых при реализации алгоритмов и объявления всех используемых контролов.

3.1 Хранение информации  о графе

 

По умолчанию  тип всех данных, используемых в  программе – int.

• a [i][j] – динамический массив содержащий матрицу смежности графа
• mas [3][20] – массив содержащий информацию о пройденных вершинах (используется при построении МОД).
• x[6] Массив, содержащий единицы и нули для каждой вершины,

(x[i]=0 - еще  не найден кратчайший путь  в i-ю вершину, x[i]=1 - кратчайший  путь в i-ю вершину уже найден).

 

• x1[20] – Массив координат по оси Х (Для расположения вершин по окружности)
• у1[20] – Массив координат по оси У (Для расположения вершин по окружности)

 

3.2 Входные и  выходные данные

 

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

6

0 0 0 0 0 9

0 0 5 0 0 0

0 5 0 20 0 7

0 0 20 0 8 1

0 0 0 8 0 1

9 0 7 1 1 0 

Рис.4 Пример входного файла gr.txt

 

Выходные  данные формируются в виде изображения. В случае нахождения минимального остова, в конце работы программы, построенный  остов  подсвечивается зелёным цветом. В случае нахождения минимального пути алгоритмом Дейкстры, минимальный путь между двумя указанными вершинами также подсвечивается зелёным цветом. Рассмотрим матрицу смежности отраженную на Рис.4, для такой матрицы смежности выходными данными будут являться изображения:

Минимальное расстояние между вершинами 2 и 4:

Рис.5 Пример определения  минимального расстояния

 

Минимальное остовное дерево для графа, заданного на Рис.4:

Рис.6 Пример построенного минимального дерева

3.3 Анализ программы

 

Ниже  мы рассмотрим основные функции, использованные в нашей программе, при реализации алгоритмов на графах:

 

void __fastcall TForm3::Button2Click(TObject *Sender) {}

При вызове этой функции открывается  диалоговое окно для выбора текстового файла с матрицей смежности.  Компонент OpenDialog1 вызывает диалоги в зависимости от выбранного файла присваивает переменной name строку с именем файла. Если значение переменной name = NULL выводится ошибка о том что файл не найден.  Далее Также данная функция заполняет матрицу смежности a[][] значениями из открытого файла и строит в компонентах Image1 и Image2 изображение графа. Image1->Canvas->MoveTo – поставить точку, Image1->Canvas->LineTo – построить из точки линию,  Image1->Canvas->TextOutA – вывести текст по заданным координатам,

Image1->Canvas->Ellipse – построить окружность, Image2->Canvas->Pen->Color/Width  – задать

цвет /ширину пера.  Рисование вершин происходит по окружности для расчёта координат рисования вершин были использованы формулы x=w+(130*cos(i*2*3.14/n)) и

y=h+(130*sin(i*2*3.14/n)), где n – число вершин графа, w – ширина окна в котором будет рисоваться граф\2, h – высота окна, в котором будет рисоваться граф\2 (переменные w,h нужны чтобы рисовать граф приблизительно посередине окна).

Входные данные – количество вершин, матрица  смежности.

Выходные  значения – координаты вершин и  смежных им ребер 

 

 

void __fastcall TForm3::Button4Click(TObject *Sender){}

Эта функция создаёт массив mas [3][n] в котором будут храниться номера вершин и минимальные веса смежных с ними ребер. Сначала функция загружает массив a[][] из файла (предполагается, что число вершин графа меньше или равно 20). Переменная k=n-1 отражает свойство минимального дерева, такое что количество ребер в МОД на единицу меньше  чем число вершин. Этот массив инициализируется: каждому a[i] [j] присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из матрицы смежности копируются в массив. При этом если в выбранном текстовом файле ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала: Создается массив versh[n]. Каждый элемент этого массива равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива versh[], кроме versh[1] равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Для этого используем цикл:

for (int i=1; i<n; i++)

for (int j=0; j<i; j++)

{

if ((a[i][j] < buf) && ((versh[i]==1) || (versh[j]==1)) && (versh[i]!=versh[j]))

{buf=a[i][j]; p=i; q=j;}

}

if (versh[p]==1) versh[q]=1; else versh[p]=1;

a[p][q]=1000;

mas[0] [kmas]=p;

mas[1] [kmas]=q;

mas[2] [kmas]=buf;

sum=sum+buf;

kmas++; k--;

}

  Алгоритм прекращает работу, когда  все вершины включены в новый  граф.

Далее функция на основании данных массива  mas[][] строит ребра, включенные в минимальное остовное дерево. Для этого используются циклы:

for (int i=0; i<n; i++)

{

x2[i]=215+(130*cos(i*2*3.14/n));

y2[i]=154+(130*sin(i*2*3.14/n));

}

for (int i=0; i<kmas; i++)

{

Image2->Canvas->MoveTo (x2[mas[1] [i]], y2[mas[1] [i]]);

Image2->Canvas->LineTo (x2[mas[0] [i]], y2[mas[0] [i]]);

}

Где x2[] y2[] – массивы координат по осям x и y соответственно.

ShowMessage("Суммарный вес пути - " + IntToStr(sum))  - функция вывода системных сообщений на экран.

Входные данные – количество вершин, матрица  смежности.

Выходные  значения – координаты вершин и  смежных им ребер составляющих минимальное остовное дерево.

 

void __fastcall TForm3::Button7Click(TObject *Sender){}

В данной функции реализован алгоритм Дейкстры. Переменная buf типа AnsiString используется для хранения вершин, включенных в минимальный маршрут между двумя вершинами. Массив mas[] используется для хранения номеров вершин в ASCII – коде. Переменная infinity по умолчанию равна 1000 (используется для обозначения пути изначально бесконечной длины). n-количество вершин в графе, s – начальная вершина, q-конечная вершина. x[]-массив, содержащий единицы и нули для каждой вершины, (x[i]=0 - еще не найден кратчайший путь в i-ю вершину, x[i]=1 - кратчайший путь в i-ю вершину уже найден), t[] содержит длину кратчайшего пути от вершины s в q, h[i] - вершина, предшествующая i-й вершине. Сначала перебираем все вершины, смежные v, и ищем для них кратчайший путь

for(u=0;u<p;u++)

  {

 if(data[v][u]==0)continue;

 if(x[u]==0 && t[u]>t[v]+data[v][u])

Если  для вершины u еще не найден кратчайший путь, и новый путь в u короче чем  старый, то: запоминаем более короткую длину пути в массив t и запоминаем, что v->u часть кратчайшего пути из s->u

t[u]=t[v]+data[v][u]; 

h[u]=v; 

}

  }

Далее  ищем из всех длин путей самый короткий, переменная w=infinity для поиска самого короткого пути. Следующий цикл перебирает все вершины и // Если для вершины не найден кратчайший путь и если длина пути в вершину u меньше уже найденной, то текущей вершиной становится u-я вершина. Заносим номер этой вершины в edit3.

  for(u=0;u<p;u++)

  {

 if(x[u]==0 && t[u]<w)

{

v=u;

w=t[u];

}

  }

  if(v==-1)

  {

 Application->MessageBox("Указанные вершиниы не имеют ребер", NULL, MB_OK);

 break;

  }

Присваиваем переменной m типа AnsiString строку из edit3.

Следующий цикл используется для занесения  в массив mas номеров вершин включенных в минимальный маршрут:

for(l=1,buf="";l<=m.Length()+1;l++)

{

  if(l==m.Length()+1)

   {

mass[k++] = StrToInt(buf);

break;

   }

  if(m[l]==' ')

   {

mass[k++] = StrToInt(buf);

buf = "";

   }

  buf += m[l];

}

Где m.Length() – длина строки компонента edit3. StrToInt() – функция преобразования текущего значения буфера из типа AnsiString в INT.

Далее, в функции производится построение только тех вершин, которые попали в минимальный маршрут(находятся в массиве mas). Построение реализовано, способом аналогичным предыдущей функции.

Входные данные – количество вершин, матрица  смежности, начальная вершина, конечная вершина.