Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

---

Принцип работы алгоритма

Дан взвешенный ориентированный граф $G(V, E)$ с неотрицательным весов рёбер. Необходимо от вершины $A$ до всех остальных вершин найти кратчайшие пути.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  ABDFECG14526108124357

Начальным значениями для всех вершин, кроме A будет $\infty$, в вершине A будет $0$:

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  ABDFECG145261081243570∞∞∞∞∞∞

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

Рекуррентная формула: $dist_Y = минимум\;из\;dist_Y\;и\;(dist_X + graph_{[X][Y]})$, где $dist_Y$ - текущее расстояние от A до Y, $graph_{[X][Y]}$ - вес ребра из X в Y

Оставшиеся шаги:

1. Рассмотрим вершину B. Пройдя в вершину B, изменится длина пути в F с бесконечности до длины пути A-B-F (13). Длина пути A-B-C (6) больше чем длина пути A-C (4), поэтому длина пути в вершину C не изменяется

2. Рассмотрим вершину C. Пройдя в эту вершину изменится длина в вершину F, ведь длина пути A-C-F (11), что меньше длины пути A-B-F (13). Длина пути в вершину D не изменится, длина пути в вершину E изменится с бесконечности до длины пути A-C-E (7).

3. Рассмотрим вершину D. Единственный доступный путь - это путь до вершины E. Но значение длины пути в вершину E не изменится, потому что длина пути A-D-E (9) больше чем длина пути A-C-E (7)

4. Рассмотрим вершину E. Значение на вершине F не изменится, потому что длина пути A-C-E-F (13) больше чем длина пути A-C-F (11). Значение длины пути до вершины G изменится с бесконечности до длины пути A-C-E-G (15)

5. Рассмотрим вершину F. Единственный доступный путь - путь в вершину G, но значение длины пути в вершину G не изменится, потому что длина пути A-C-F-G (21) больше чем длина пути A-C-E-G (15)

6. Рассмотрим вершину G. Из неё нет доступных путей.

7. В результате действия алгоритма получим следующий граф:

Значения длин путей до вершин будут храниться в массиве $dist$ размерности V

---

Вычислительная сложность

Сложность алгоритма Дейкстры зависит от способа нахождения вершины $v$, а также способа хранения множества не посещённых вершин и способа обновления меток.

1. В простейшем случае, когда для поиска вершины с минимальным $d[v]$ просматривается всё множество вершин, а для хранения величин $d$ используется массив, сложность равна $O(n^2)$

2. Для разреженных графов (то есть таких, для которых m много меньше $n^2$) не посещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения $d_[i]$, тогда сложность равна $O(n log n+m log n)$

3. Если использовать Фибоначчиеву кучу, чтобы хранить непосещённые вершны, то сложность равна $O(n log n +m)$

---

Псевдокод

Аннотация:
graph - матрица смежности, в которой гранится граф
dist - массив оптимальных значений
amount - количество вершин
start - вершина, до которой необходимо посчитать кратчайшие пути до всех остальных
visited - массив булевых значений, в котором помечаются все посещённые вершины

функция алгоритм_дейкстры(graph):
    заполнение массива dist размерности amount бесконечностями
    dist[start] <- 0
    заполнение массива visited размерности amount "Ложь"
    
    для k от 0 до amount:
        min_dist <- "Бесконечность"
        min_index <- -1
        
        для i от 0 до amount:
            если (не visited[i]) и (dist[i] < min_dist), то
                min_dist <- dist[i]
                min_index <- i
        
        visited[min_index] = True
        для i от 0 до amount:
            если (graph[min_index][i] не равен 0) и (не visited[i]), то
                dist[i] <- минимум из dist[i] и (dist[min_index] + graph[min_index][i])
    
    вернуть dist

---

Реализация на Python

Аннотация:
dijkstra - алгоритм Дейкстры
graph - матрица смежности, в которой хранится граф
start - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
dist -  массив оптимальных значений
inf - константа, равная бесконечности
visited - массив булевых значений, в котором помечаются все посещённые вершины

def dijkstra(graph, start):
    dist = [inf] * len(graph)
    dist[start] = 0
    visited = [False] * len(graph)

    for _ in range(len(graph)):
        min_dist = inf
        min_index = -1

        for i in range(len(graph)):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                min_index = i

        visited[min_index] = True
        for i in range(len(graph)):
            if graph[min_index][i] != 0 and not visited[i]:
                dist[i] = min(
                    dist[i], dist[min_index] + graph[min_index][i])

    return dist

---

Олимпиадная реализация на C++

Аннотация:
dijkstra - алгоритм Дейкстры
g - матрица смежности, в которой хранится граф
s - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
n - количество вершин
dist - массив оптимальных значений
visited - массив булевых значений, в котором помечаются все посещённые вершины

vector<int> dijkstra(const vector<vector<int>> &g, int s) {
    const int MAX_INT = numeric_limits<int>::max();
    int n = g.size();
    vector<int> dist(n, MAX_INT);
    vector<bool> visited(n, false);
    dist[s] = 0;
    for (int i = 0; i < n; ++i) {
        int min_dist = MAX_INT;
        int min_i = -1;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_i = j;
            }
        }
        if (min_i == -1)
            break;
        visited[min_i] = true;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && g[min_i][j] != MAX_INT) 
                dist[j] = min(dist[j], dist[min_i] + g[min_i][j]);
        }
    }
    return dist;
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
dijkstra - алгоритм Дейкстры
graph - матрица смежности, в которой хранится граф
start - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
MAX_INT - константа, равная бесконечности
amount - количество вершин
dist -  массив оптимальных значений
visited - массив булевых значений, в котором помечаются все посещённые вершины

template<typename ValueType>
std::vector<ValueType> dijkstra(const std::vector<std::vector<ValueType>> &graph, ValueType start) {
    const int MAX_INT = std::numeric_limits<ValueType>::max();
    int amount = graph.size();
    std::vector<ValueType> dist(amount, MAX_INT);
    std::vector<bool> visited(amount, false);
    dist[start] = 0;

    for (int i = 0; i < amount; ++i) {
        ValueType min_dist = MAX_INT;
        int min_index = -1;

        for (int j = 0; j < v; ++j) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }

        if (min_index == -1)
            break;

        visited[min_index] = true;
        for (int j = 0; j < amount; ++j) {
            if (!visited[j] && graph[min_index][j] != MAX_INT)
                dist[j] = std::min(dist[j], dist[min_index] + graph[min_index][j]);
        }
    }

    return dist;
}