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

Алгоритм кратчайшего пути Дейкстры

Прежде чем продолжить, рекомендуется иметь краткое представление о матрице смежности и BFS

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

Мы можем найти кратчайший путь, используя алгоритм поиска Breadth First Search (BFS). Этот алгоритм работает отлично, но проблема в том, что он предполагает, что стоимость прохождения каждого пути одинакова, что означает, что стоимость каждого ребра одинакова. Алгоритм Дейкстры помогает найти кратчайший путь, где стоимость каждого пути не совпадает.

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

Скажем, расстояние каждого узла от источника сохраняется в массиве d [] . Как и в, d [3] означает, что d [3] время для достижения узла 3 из источника . Если мы не знаем расстояния, мы сохраним бесконечность в d [3] . Кроме того, пусть стоимость [u] [v] отражает стоимость uv . Это означает, что для перехода от узла u к v требуется стоимость [u] [v] .

Нам нужно понять релаксацию края. Скажем, из вашего дома, источника , требуется 10 минут, чтобы пойти на место A. И это займет 25 минут, чтобы пойти на место B. У нас есть,

d[A] = 10
d[B] = 25

Теперь предположим, что от места A до места B требуется 7 минут, это означает:

cost[A][B] = 7

Затем мы можем поместить B из источника , перейдя на место A из источника, а затем из места A , идя на место B , которое займет 10 + 7 = 17 минут, вместо 25 минут. Так,

d[A] + cost[A][B] < d[B]

Затем мы обновляем,

d[B] = d[A] + cost[A][B]

Это называется расслаблением. Мы перейдем от узла u к узлу v, а если d [u] + cost [u] [v] <d [v], то мы обновим d [v] = d [u] + cost [u] [v] .

В BFS нам не нужно было посещать какой-либо узел дважды. Мы только проверяли, посетил ли узел или нет. Если он не был посещен, мы переместили узел в очередь, пометили его как посетили и увеличили расстояние на 1. В Dijkstra мы можем нажать узел в очереди и вместо обновления его посещением, мы расслабляем или обновляем новый край. Давайте рассмотрим один пример:

Предположим, что Node 1 является источником . Затем,

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

Мы установили d [2], d [3] и d [4] на бесконечность, потому что мы еще не знаем расстояния. И расстояние от источника, конечно, 0 . Теперь мы переходим к другим узлам из исходного кода, и если мы можем их обновить, мы будем выталкивать их в очередь. Скажем, например, мы пройдем к краю 1-2 . Как d [1] + 2 <d [2], что сделает d [2] = 2 . Точно так же мы будем пересекать край 1-3, что делает d [3] = 5 .

Мы можем ясно видеть, что 5 - это не кратчайшее расстояние, которое мы можем пересечь, чтобы перейти к узлу 3 . Поэтому перемещение узла только один раз, как BFS, здесь не работает. Если перейти от узла 2 к узлу 3 с использованием ребра 2-3 , мы можем обновить d [3] = d [2] + 1 = 3 . Таким образом, мы видим, что один узел может обновляться много раз. Сколько раз вы спрашиваете? Максимальное количество раз, когда узел может быть обновлен, - это количество встроенных узлов.

Давайте посмотрим на псевдокод для посещения любого узла несколько раз. Мы просто изменим BFS:

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

Это можно использовать для поиска кратчайшего пути всего узла из источника. Сложность этого кода не так хороша. Вот почему,

В BFS, когда мы переходим от узла 1 ко всем другим узлам, мы следуем первому методу first serve . Например, мы перешли к узлу 3 из источника перед обработкой узла 2 . Если мы перейдем к узлу 3 из источника , мы обновим узел 4 как 5 + 3 = 8 . Когда мы снова обновляем узел 3 из узла 2 , нам нужно снова обновить узел 4 как 3 + 3 = 6 ! Поэтому узел 4 обновляется дважды.

Дейкстра предложил вместо того, чтобы идти первым, первым подавать метод, если сначала обновить ближайшие узлы, тогда это займет меньше обновлений. Если бы мы обработали узел 2 раньше, то узел 3 был бы обновлен до этого, и после обновления узла 4 соответственно мы легко получили бы кратчайшее расстояние! Идея состоит в том, чтобы выбрать из очереди, ближайший к источнику узел. Поэтому мы будем использовать Priority Queue здесь, чтобы, когда мы выходим в очередь, это принесет нам ближайший узел u из источника . Как он это сделает? Он проверит значение d [u] с ним.

Давайте посмотрим на псевдокод:

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

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

Теперь, работает ли алгоритм Дейкстры, когда есть отрицательное ребро? Если есть отрицательный цикл, тогда будет цикл бесконечности, так как он будет продолжать уменьшать стоимость каждый раз. Даже если есть отрицательный фронт, Dijkstra не будет работать, если мы не вернемся сразу после того, как цель выскочит. Но тогда это не будет алгоритм Дейкстры. Нам понадобится алгоритм Bellman-Ford для обработки отрицательного края / цикла.

Сложность:

Сложность BFS - O (log (V + E)), где V - число узлов, а E - количество ребер. Для Dijkstra сложность аналогична, но сортировка очереди приоритетов принимает O (logV) . Таким образом, общая сложность: O (Vlog (V) + E)

Ниже приведен пример Java для решения алгоритма кратчайшего пути Дейкстры с использованием матрицы смежности

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    void dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

Ожидаемый результат программы

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14