15. Теория графов. Алгоритм Дейкстры.

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

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 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 < 17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

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

Третий шаг.

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг.

Пятый шаг.

Шестой шаг.

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

Фрагмент кода:

int start = 0;
int end = 0;
Console.Write("Введите N=");
int n = Convert.ToInt32(Console.ReadLine());

int[,] graf = new int[n, n];

Console.Write("Введите M=");
int m = Convert.ToInt32(Console.ReadLine());

for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}

Console.Write("Введите X=");
start = Convert.ToInt32(Console.ReadLine());

Console.Write("Введите Y=");
end = Convert.ToInt32(Console.ReadLine());

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

Boolean[] uses = new Boolean[n];

path[start] = 0;
int usesCount = 0;
while (usesCount < n)
{
    int min = Int32.MaxValue;
    int current=0;
    for (int i = 0; i < n; i++)
    {
        if (!uses[i] && path[i] < min)
        {
            min = path[i];
            current = i;
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        if (graf[current, i] > 0 && !uses[i])
        {
            if (path[current] + graf[current, i] < path[i])
            {
                path[i] = path[current] + graf[current, i];
            }
        }
    }

    uses[current] = true;
    usesCount++;
}

for (int i = 0; i < n; i++)
{
    Console.WriteLine(i + " - " + path[i]);
}

Console.WriteLine("Ответ: " + path[end]);

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

Задание: Попробуйте самостоятельно реализовать алгоритм Дейкстры для ориентированного графа (каждое ребро задает движение только в одном направлении: от первой указанной вершины до второй).

Итоги занятия.