Кратчайшие пути в ориентированных графах

 

 

2.3 Алгоритм Дейкстры

 

Алгоритм Дейкстры позволяет найти кратчайшие пути от данной вершины до всех остальных вершин в графе. Алгоритм состоит из следующих шагов:

1. положить для всех вершин (кроме исходной) расстояние равное бесконечности, для исходной присвоить нулю;
2. выбрать непомеченную вершину , с минимальным расстоянием. Если такой вершины нет, то завершить работу;
3. пометить вершину ;
4. для всех непомеченных вершин, смежных с вершиной , попытаться уменьшить расстояние;
5. вернуться к шагу 2; [2]

Пример – Алгоритм Дейкстра.

Дан взвешенный ориентированный граф  , без петель и дуг отрицательного веса в соответствии с рисунком 3. Найти кратчайшие пути от некоторой вершины  графа  до всех остальных вершин этого графа. [4]

Рисунок 3 – Граф.

Каждой вершине из  сопоставим метку – минимальное известное расстояние от этой вершины до . Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Шаг 1. Метка самой вершины  полагается равной 0, метки остальных вершин – бесконечности. Это отражает то, что расстояния от  до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.

Шаг 2. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина , имеющая минимальную метку. Вершины, в которые ведут рёбра из  , назовем соседями этой вершины. Для каждого соседа вершины  , кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки  и длины ребра, соединяющего  с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину  как посещенную и повторим шаг алгоритма.

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

Рисунок 4 –Пример графа.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» – длина пути. Рядом с каждой вершиной обозначена метка – длина кратчайшего пути в эту вершину из вершины 1(см. рисунок 5).

Рисунок 5 – Метки вершин.

Шаг 3. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6 согласно рисунку 6.

Рисунок 6 – Соседи вершины 1.

Шаг 4. Первый по очереди сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна согласно рисунку 7. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Рисунок 7 – Вершина 2.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины – 3-й как показано на рисунке 7 и 6-й согласно рисунку 8.

Рисунок 8 – Действия с соседями.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вычеркнем её из графа, чтобы отметить, что эта вершина посещена (см. рисунок 9).

Рисунок 9 – Вычеркивание вершины 1.

Шаг 5. Снова находим «ближайшую» из не посещенных вершин. Это вершина 2 с меткой 7 как указано на рисунке 10.

Рисунок 10 – Помечаем вершину 2.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 – вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 – вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется рисунок 11.

Рисунок 11 – Изменение текущей метки.

 
Ещё один сосед вершины 2 – вершина 4 (см. рисунок 12). Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть . Поскольку , устанавливаем метку вершины 4 равной 22.

Рисунок 12 – Метка вершины 4.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную (см. рисунок 13).

Рисунок 13 – Посещенная вершина 2.

Повторяем алгоритм, выбрав вершину 3 рисунок 14. После её «обработки» получим такие результаты (см. рисунок 15):

Рисунок 14 – Вершина 3.

Дальнейшие шаги рисунок 15. Повторяем алгоритм для оставшихся вершин (см. рисунок 16).

Рисунок 15 – Посещенная вершина 3.

Рисунок 16 – Повторение алгоритма.

Рисунок 17 – Завершение алгоритма.

Завершение выполнения алгоритма (см. рисунок 17). Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины (см.рисунок 17). В данном примере все вершины зачеркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться не зачеркнутыми, если до них нельзя добраться. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й – 9, до 4-й – 20, до 5-й – 20, до 6-й – 11.

Доказательство корректности алгоритма Дейкстры.

Пусть  – длина кратчайшего пути из вершины в вершину . Докажем по индукции, что в момент посещения любой вершины , . 
Первой посещается вершина . В этот момент . 
Пускай мы выбрали для посещения вершину . Докажем, что в этот момент . Для начала отметим, что для любой вершины , всегда выполняется  (алгоритм не может найти путь короче, чем кратчайший из всех существующих ). Пусть  – кратчайший путь из в ,  – первая не посещённая вершина на ,  – предшествующая ей (следовательно, посещённая). Поскольку путь кратчайший, его часть, ведущая из через в , тоже кратчайшая, следовательно . По предположению индукции, в момент посещения вершины выполнялось , следовательно, вершина y тогда получила метку не больше чем                 . Следовательно, . С другой стороны, поскольку сейчас мы выбрали вершину , её метка минимальна среди не посещённых, то есть . Комбинируя это с       , имеем , что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент для всех вершин.

 

3 Программная реализация алгоритма Дейкстры

 

 

В приложении А к курсовой работе представлена реализация алгоритма Дейкстра на языке программирования С++. В этом разделе приведена подробная инструкция к программе, которая находит кратчайшие пути в ориентированном графе от заданной вершины до всех остальных. При запуске программы в открытом окне требуется ввести количество вершин в графе (см.рисунок 18).

Рисунок 18 – Введите вершины.

Далее требуется ввести матрицу смежности графа (см. рисунок 19).

Рисунок 19 – Введите матрицу смежности.

Введите начальную вершину, из которой требуется найти кратчайший путь (см. рисунок 20).

Рисунок 20 – Введите начальную вершину графа.

Далее на экран выводится кратчайшие пути от заданной начальной вершины до всех остальных вершин (см. рисунок 21).

Рисунок 21 – Вывод результата.

В случае отсутствия решения или некорректно введенных данных, программа выдаст сообщение: «Маршрут недоступен» (см. рисунок 22).

Рисунок 22 – Ошибка.

 

ЗАКЛЮЧЕНИЕ

 

Обширное применение теория графов находит в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ, баз данных, систем логического управления. В приложениях часто приходится рассматривать графы с ориентированными ребрами. Примерами таких графов являются сети автомобильных дорог с односторонним движением или схемы программ для ЭВМ.

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

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

 

1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука. Физматлит, 1997. – 368 с. – ISBN 5-02-015033-9.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука. Гл. ред. физ.- мат. лит., 1990. – 384 с. – ISBN 5-02-013992-0.
3. Томас Х. Кормен., Чарльз И. Лейзерсон., Алгоритмы: построение и анализ. Учебное пособие, 2-е изд., — М.: Вильямс, 2006. —1296 с. — ISBN 0-07-013151-1
4. Алгоритм Дейкстра [Электронный ресурс] // Википедия свободная энциклопедия [Электронный ресурс] : полнотекстовая ВСЭ с картинками. URL: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры (дата обращения: 12.05.2013). Загл. с экрана. Яз.рус

 

Приложение А.

Листинг программы

 

#include <cmath>

#include<clocale>

#include <iostream>

using namespace std;

const int V=100;

//алгоритм Дейкстры

void Dijkstra(int GR[V][V], int st,int n)

{

int distance[V], count, index, i, u, m=st+1;

bool visited[V];

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

{

distance[i]=INT_MAX; visited[i]=false;

}

distance[st]=0;

for (count=0; count<n-1; count++)

{

int min=INT_MAX;

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

if (!visited[i] && distance[i]<=min)

{

min=distance[i]; index=i;

}

u=index;

visited[u]=true;

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

if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&

distance[u]+GR[u][i]<distance[i])

distance[i]=distance[u]+GR[u][i];

}

cout<<"Стоимость пути из начальной вершины до остальных:\t\n";

for (i=0; i<n; i++) if (distance[i]!=INT_MAX)

cout<<m<<" > "<<i+1<<" = "<<distance[i]<<endl;

else cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl;

}

//главная функция

void main()

{

setlocale(LC_ALL, "Rus");

int start; int GR[V][V]; int n; cin>>n;

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

for(int j=0; j<n;j++){

cin>>GR[i][j];}}

 

cout<<"Начальная вершина >> "; cin>>start;

Dijkstra(GR, start-1,n);

system("pause>>void");}