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

Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.

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

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

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

Инициализация

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

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

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

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

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

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

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 Реализация на C++

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
<
int a[SIZE][SIZE]; // матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system( «chcp 1251» );
system( «cls» );
// Инициализация матрицы связей
for ( int i = 0; i for ( int j = i + 1; j «Введите расстояние %d — %d: » , i + 1, j + 1);
scanf( «%d» , &temp);
a[i][j] = temp;
a[j][i] = temp;
>
>
// Вывод матрицы связей
for ( int i = 0; i for ( int j = 0; j «%5d » , a[i][j]);
printf( «\n» );
>
//Инициализация вершин и расстояний
for ( int i = 0; i // Шаг алгоритма
do <
minindex = 10000;
min = 10000;
for ( int i = 0; i // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i] // Переприсваиваем значения
min = d[i];
minindex = i;
>
>
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
<
for ( int i = 0; i if (a[minindex][i] > 0)
<
temp = min + a[minindex][i];
if (temp while (minindex // Вывод кратчайших расстояний до вершин
printf( «\nКратчайшие расстояния до вершин: \n» );
for ( int i = 0; i «%5d » , d[i]);

// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 — 1
ver[0] = end + 1; // начальный элемент — конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины

while (end != begin_index) // пока не дошли до начальной вершины
<
for ( int i = 0; i // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
<
int temp = weight — a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
< // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
>
>
>
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf( «\nВывод кратчайшего пути\n» );
for ( int i = k — 1; i >= 0; i—)
printf( «%3d » , ver[i]);
getchar(); getchar();
return 0;
>

Реализация алгоритма Дейкстры на C#

Введение

Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.

UPDНаконец-то подчистил код 🙂

Немного теории

Начало

Данный код представляет реализацию алгоритма на взвешенном неориентированном графе. Рассмотрим реализацию этого алгоритма.
Объектами данного алгоритма являются три класса:
• Apoint – класс, реализующий вершину графа
• Rebro – класс, реализующий ребро графа
• DekstraAlgoritm – класс, реализующий алгоритм Дейкстры.
Рассмотрим подробнее данные классы и самые важные методы.
APoint
Данный класс содержит в себе 5 полей:
•public float ValueMetka < get; set; >данное поле отвечает за хранение значений метки данной вершины. В программе под бесконечностью берется очень большое число, например 99999.
•public string Name < get; set; >– имя метки. Данное поле необходимо лишь для выведения удобно читаемого результата.
•public bool IsChecked < get; set; >– означает помечена метка или нет
•public APoint predPoint < get; set; >– «предок» точки, т.е. та точка которая является предком текущей в кратчайшем маршруте.
•public object SomeObj < get; set; >– некий объект
Каких-либо значимых методов данный класс не содержит.
Rebro
Данный класс содержит 3 поля:
•public APoint FirstPoint < get; set; >– начальная вершина ребра
•public APoint SecondPoint < get; set; >– конечная вершина ребра
•public float Value < get; set; >– весовой коэффициент.
Каких-либо значимых методов данный класс не содержит.
DekstraAlgorim
Данный класс представляет собой граф и реализацию алгоритма Дейкстры. Содержит 2 поля:
•public APoint[] points < get; set; >– массив вершин
•public Rebro[] rebra < get; set; >— массив ребер
Таким образом, эти 2 массива отражают граф. Рассмотрим методы:
•private APoint GetAnotherUncheckedPoint()
Данный метод возвращает очередную неотмеченную вершину, наименее удаленную, согласно алгоритму.
•public void OneStep(APoint beginpoint)
Данный метод делает один шаг алгоритма для заданной точке.
•private IEnumerable Pred(APoint currpoint)
Данный метод ищет соседей для заданной точки и возвращает коллекцию точек.
•public string MinPath(APoint begin,APoint end)
Данный метод возвращает кратчайший путь, найденный в алгоритме от начальной точке до конечной. Этот метод используется для наглядного отображения пути
•public void AlgoritmRun(APoint beginp)
Данный метод запускает алгоритм и принимает в качестве входа начальную точку.
Все основные методы описаны, представим процесс работы алгоритма в целом на рис.1. Основной метод OneStep представлен на рисунке 2.

Рис.1. Работа алгоритма в целом

Рис.2. Работа метода OneStep

///
/// Реализация алгоритма Дейкстры. Содержит матрицу смежности в виде массивов вершин и ребер
///
class DekstraAlgorim
<

public Point[] points < get ; private set ; >
public Rebro[] rebra < get ; private set ; >
public Point BeginPoint

public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
<
points = pointsOfgrath;
rebra = rebraOfgrath;
>
///
/// Запуск алгоритма расчета
///
///

public void AlgoritmRun(Point beginp)
<
if ( this .points.Count() == 0 || this .rebra.Count() == 0)
<
throw new DekstraException( «Массив вершин или ребер не задан!» );
>
else
<
BeginPoint = beginp;
OneStep(beginp);
foreach (Point point in points)
<
Point anotherP = GetAnotherUncheckedPoint();
if (anotherP != null )
<
OneStep(anotherP);
>
else
<
break ;
>

>
///
/// Метод, делающий один шаг алгоритма. Принимает на вход вершину
///
///

public void OneStep(Point beginpoint)
<
foreach (Point nextp in Pred(beginpoint))
<
if (nextp.IsChecked == false ) //не отмечена
<
float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
if (nextp.ValueMetka > newmetka)
<
nextp.ValueMetka = newmetka;
nextp.predPoint = beginpoint;
>
else
<

>
>
>
beginpoint.IsChecked = true ; //вычеркиваем
>
///
/// Поиск соседей для вершины. Для неориентированного графа ищутся все соседи.
///
///

Pred(Point currpoint)
<
IEnumerable

firstpoints = from ff in rebra where ff.FirstPoint==currpoint select ff.SecondPoint;
IEnumerable

secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
IEnumerable

(secondpoints);
return totalpoints;
>
///
/// Получаем ребро, соединяющее 2 входные точки
///
///

///
private Rebro GetMyRebro(Point a, Point b)
< //ищем ребро по 2 точкам
IEnumerable myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
if (myr.Count() > 1 || myr.Count() == 0)
<
throw new DekstraException( «Не найдено ребро между соседями!» );
>
else
<
return myr.First();
>
>
///
/// Получаем очередную неотмеченную вершину, «ближайшую» к заданной.
///
///
private Point GetAnotherUncheckedPoint()
<
IEnumerable

pointsuncheck = from p in points where p.IsChecked == false select p;
if (pointsuncheck.Count() != 0)
<
float minVal = pointsuncheck.First().ValueMetka;
Point minPoint = pointsuncheck.First();
foreach (Point p in pointsuncheck)
<
if (p.ValueMetka return minPoint;
>
else
<
return null ;
>
>

MinPath1(Point end)
<
List

listOfpoints = new List

();
Point tempp = new Point();
tempp = end;
while (tempp != this .BeginPoint)
<
listOfpoints.Add(tempp);
tempp = tempp.predPoint;
>