algorithm
Algorytm Dijkstry

Algorytm najkrótszej ścieżki Dijkstry

Przed kontynuowaniem zaleca się krótkie zapoznanie się z Matrycą Adjacencji i BFS

Algorytm Dijkstry jest znany jako algorytm najkrótszej ścieżki z jednego źródła. Służy do znajdowania najkrótszych ścieżek między węzłami na wykresie, które mogą reprezentować na przykład sieci drogowe. Został opracowany przez Edsger W. Dijkstra w 1956 roku i opublikowany trzy lata później.

Najkrótszą ścieżkę możemy znaleźć, korzystając z algorytmu przeszukiwania szerokości pierwszego wyszukiwania (BFS). Ten algorytm działa dobrze, ale problem polega na tym, że zakłada on, że koszt przejścia każdej ścieżki jest taki sam, co oznacza, że koszt każdej krawędzi jest taki sam. Algorytm Dijkstry pomaga nam znaleźć najkrótszą ścieżkę, w której koszt każdej ścieżki nie jest taki sam.

Najpierw zobaczymy, jak zmodyfikować BFS, aby zapisać algorytm Dijkstry, a następnie dodamy kolejkę priorytetową, aby uczynić go kompletnym algorytmem Dijkstry.

Powiedzmy, że odległość każdego węzła od źródła jest utrzymywana w tablicy d [] . Jak w, d [3] oznacza, że potrzeba d [3] dotarcia do węzła 3 ze źródła . Jeśli nie znamy odległości, przechowujemy nieskończoność w d [3] . Niech też koszt [u] [v] reprezentuje koszt uv . Oznacza to, że zajmuje koszty [U] [V], aby przejść od węzła u do v węzła.

Musimy zrozumieć Edge Relaxation. Powiedzmy, że z twojego domu, który jest źródłem , przejście do miejsca A. zajmuje 10 minut. I zajmuje 25 minut, aby przejść do miejsca B. Mamy,

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

Powiedzmy, że przejście z miejsca A do miejsca B zajmuje 7 minut, co oznacza:

cost[A][B] = 7

Następnie możemy przejść do miejsca B ze źródła , przechodząc do miejsca A ze źródła, a następnie z miejsca A , przechodząc do miejsca B , co zajmie 10 + 7 = 17 minut, zamiast 25 minut. Więc,

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

Następnie aktualizujemy,

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

To się nazywa relaksacja. Przejdziemy od węzła u do węzła v, a jeśli d [u] + koszt [u] [v] <d [v], wówczas zaktualizujemy d [v] = d [u] + cost [u] [v] .

W BFS nie musieliśmy dwukrotnie odwiedzać żadnego węzła. Sprawdziliśmy tylko, czy węzeł jest odwiedzany, czy nie. Jeśli nie był odwiedzany, wepchnęliśmy węzeł do kolejki, oznaczyliśmy go jako odwiedzony i zwiększyliśmy odległość o 1. W Dijkstra możemy przesunąć węzeł w kolejce i zamiast aktualizować go o odwiedzone, rozluźnimy lub zaktualizujemy nową krawędź. Spójrzmy na jeden przykład:

Załóżmy, że węzeł 1 jest źródłem . Następnie,

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

Ustawiamy, d [2], d [3] id [4] na nieskończoność, ponieważ jeszcze nie znamy odległości. Odległość źródła wynosi oczywiście 0 . Teraz przechodzimy do innych węzłów ze źródła i jeśli możemy je zaktualizować, wówczas popchniemy je w kolejce. Powiedzmy na przykład, że przejdziemy przez krawędź 1-2 . Jako d [1] + 2 <d [2], co spowoduje, że d [2] = 2 . Podobnie przejdziemy przez krawędź 1-3, co powoduje, że d [3] = 5 .

Widzimy wyraźnie, że 5 nie jest najmniejszą odległością, jaką możemy pokonać, aby przejść do węzła 3 . Przejście węzła tylko raz, jak BFS, tutaj nie działa. Jeśli przejdziemy od węzła 2 do węzła 3 za pomocą krawędzi 2-3 , możemy zaktualizować d [3] = d [2] + 1 = 3 . Widzimy więc, że jeden węzeł może być aktualizowany wiele razy. Ile razy pytasz? Maksymalna liczba aktualizacji węzła to liczba stopni węzła.

Zobaczmy pseudo-kod do wielokrotnego odwiedzania dowolnego węzła. Po prostu zmodyfikujemy 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

Można to wykorzystać do znalezienia najkrótszej ścieżki ze wszystkich węzłów. Złożoność tego kodu nie jest tak dobra. Dlatego,

W BFS, gdy przechodzimy od węzła 1 do wszystkich innych węzłów, stosujemy metodę „ kto pierwszy, ten lepszy” . Na przykład przeszliśmy do węzła 3 ze źródła przed przetworzeniem węzła 2 . Jeśli przejdziemy do węzła 3 ze źródła , aktualizujemy węzeł 4 jako 5 + 3 = 8 . Kiedy ponownie zaktualizujemy węzeł 3 z węzła 2 , musimy ponownie zaktualizować węzeł 4 jako 3 + 3 = 6 ! Węzeł 4 jest aktualizowany dwukrotnie.

Dijkstra zaproponował zamiast metody „ kto pierwszy, ten lepszy” , jeśli najpierw zaktualizujemy najbliższe węzły, zajmie to mniej aktualizacji. Gdybyśmy wcześniej przetwarzali węzeł 2 , wówczas węzeł 3 byłby aktualizowany wcześniej, a po odpowiedniej aktualizacji węzła 4 z łatwością uzyskalibyśmy najmniejszą odległość! Chodzi o to, aby wybrać z kolejki, węzeł, który jest najbliżej źródła . Dlatego użyjemy tutaj kolejki priorytetowej , aby po przejechaniu kolejki przyniosła nam najbliższy węzeł u ze źródła . Jak to zrobi? Za jego pomocą sprawdzi wartość d [u] .

Zobaczmy pseudo-kod:

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

Pseudokod zwraca odległość wszystkich innych węzłów od źródła . Jeśli chcemy poznać odległość pojedynczego węzła v , możemy po prostu zwrócić wartość, gdy v wyskoczy z kolejki.

Czy algorytm Dijkstry działa, gdy występuje ujemna przewaga? Jeśli występuje cykl ujemny, pojawi się pętla nieskończoności, która za każdym razem będzie obniżać koszt. Nawet jeśli jest ujemna przewaga, Dijkstra nie będzie działać, chyba że wrócimy zaraz po wyskoku celu. Ale wtedy nie będzie to algorytm Dijkstry. Będziemy potrzebować algorytmu Bellmana-Forda do przetwarzania ujemnego zbocza / cyklu.

Złożoność:

Złożoność BFS to O (log (V + E)), gdzie V to liczba węzłów, a E to liczba krawędzi. W przypadku Dijkstry złożoność jest podobna, ale sortowanie kolejki priorytetowej zajmuje O (logV) . Zatem całkowita złożoność wynosi: O (Vlog (V) + E)

Poniżej znajduje się przykład Java do rozwiązania algorytmu najkrótszej ścieżki Dijkstry za pomocą matrycy adiakencji

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);
    }
}

Oczekiwany wynik programu to

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