algorithm
Dijkstra's algoritme

Dijkstra's kortste padalgoritme

Voordat u doorgaat, is het raadzaam om een kort idee te hebben van Adjacency Matrix en BFS

Het algoritme van Dijkstra staat bekend als single-source shortest path algoritme. Het wordt gebruikt voor het vinden van de kortste paden tussen knooppunten in een grafiek, die bijvoorbeeld wegennetwerken kunnen vertegenwoordigen. Het werd bedacht door Edsger W. Dijkstra in 1956 en drie jaar later gepubliceerd.

We kunnen het kortste pad vinden met behulp van het BTH-zoekalgoritme van Breadth First Search (BFS). Dit algoritme werkt prima, maar het probleem is dat het ervan uitgaat dat de kosten van het doorlopen van elk pad hetzelfde zijn, wat betekent dat de kosten van elke rand hetzelfde zijn. Het algoritme van Dijkstra helpt ons om het kortste pad te vinden waarbij de kosten van elk pad niet hetzelfde zijn.

Eerst zullen we zien hoe we BFS kunnen aanpassen om het algoritme van Dijkstra te schrijven, daarna zullen we een prioriteitswachtrij toevoegen om er een compleet algoritme van Dijkstra van te maken.

Laten we zeggen dat de afstand van elk knooppunt tot de bron wordt bewaard in de array d [] . Zoals in, d [3] betekent dat d [3] tijd genomen om te bereiken knooppunt 3 van de bron. Als we de afstand niet weten, slaan we oneindigheid op in d [3] . Laat kosten [u] [v] ook de kosten van uv vertegenwoordigen . Dat betekent dat het kosten kost [u] [v] om van u- knoop naar v- knoop te gaan.

We moeten Edge Relaxation begrijpen. Laten we zeggen, vanuit uw huis, dat is de bron , het duurt 10 minuten om naar plaats A te gaan. En het duurt 25 minuten om naar plaats B te gaan. Wij hebben,

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

Laten we zeggen dat het 7 minuten duurt om van plaats A naar plaats B te gaan , dat betekent:

cost[A][B] = 7

Dan kunnen we gaan naar plaats B van de bron door te gaan naar een plaats van de bron en vervolgens van plaats A, naar plaats B, waarvan 10 + 7 = 17 minuten, in plaats van 25 minuten in beslag neemt. Zo,

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

Dan updaten we,

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

Dit wordt ontspanning genoemd. We gaan van knooppunt u naar knooppunt v en als d [u] + kosten [u] [v] <d [v] , werken we d [v] = d [u] + kosten [u] [v] bij .

In BFS hoefden we geen enkel knooppunt twee keer te bezoeken. We hebben alleen gecontroleerd of een knooppunt is bezocht of niet. Als het niet werd bezocht, duwden we het knooppunt in de wachtrij, markeerden het als bezocht en verhoogden we de afstand met 1. In Dijkstra kunnen we een knooppunt in de wachtrij duwen en in plaats van bij te werken met bezocht, ontspannen we of updaten we de nieuwe rand. Laten we een voorbeeld bekijken:

Laten we aannemen dat knooppunt 1 de bron is . Vervolgens,

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

We stellen d [2], d [3] en d [4] in op oneindig omdat we de afstand nog niet kennen. En de afstand van de bron is natuurlijk 0 . Nu gaan we naar andere knooppunten van bron en als we ze kunnen bijwerken, zullen we ze in de wachtrij plaatsen. Zeg bijvoorbeeld dat we rand 1-2 zullen doorkruisen. Als d [1] + 2 <d [2] waardoor d [2] = 2 wordt . Op dezelfde manier zullen we rand 1-3 doorkruisen waardoor d [3] = 5 wordt .

We kunnen duidelijk zien dat 5 niet de kortste afstand is die we kunnen overbruggen om naar knooppunt 3 te gaan. Dus het oversteken van een knooppunt, zoals BFS, werkt hier niet. Als we met rand 2-3 van knooppunt 2 naar knooppunt 3 gaan , kunnen we d [3] = d [2] + 1 = 3 bijwerken. We kunnen dus zien dat één knooppunt vele malen kan worden bijgewerkt. Hoe vaak vraag je dat? Het maximale aantal keren dat een knooppunt kan worden bijgewerkt, is het aantal in-graden van een knooppunt.

Laten we de pseudocode bekijken voor het meerdere keren bezoeken van een knooppunt. We zullen eenvoudig BFS wijzigen:

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

Dit kan worden gebruikt om het kortste pad van alle knooppunten van de bron te vinden. De complexiteit van deze code is niet zo goed. Dit is waarom,

Als we in BFS van knooppunt 1 naar alle andere knooppunten gaan, volgen we de methode wie het eerst komt, het eerst maalt . We zijn bijvoorbeeld vanaf de bron naar knooppunt 3 gegaan voordat knooppunt 2 is verwerkt. Als we vanaf de bron naar knooppunt 3 gaan, werken we knooppunt 4 bij als 5 + 3 = 8 . Wanneer we knooppunt 3 opnieuw bijwerken vanaf knooppunt 2 , moeten we knooppunt 4 opnieuw bijwerken als 3 + 3 = 6 ! Knooppunt 4 wordt dus twee keer bijgewerkt.

Dijkstra stelde voor, in plaats van te kiezen voor wie het eerst komt, het eerst maalt , als we eerst de dichtstbijzijnde knooppunten bijwerken, dan zijn er minder updates nodig. Als we knooppunt 2 eerder hadden verwerkt, zou knooppunt 3 eerder zijn bijgewerkt, en na knooppunt 4 dienovereenkomstig bij te werken, zouden we gemakkelijk de kortste afstand krijgen! Het idee is om te kiezen uit de wachtrij, het knooppunt dat het dichtst bij de bron ligt . Dus we Priority Queue hier zal gebruiken, zodat wanneer we de wachtrij pop, het zal ons de dichtstbijzijnde knooppunt u van de bron. Hoe gaat het dat doen? Hiermee wordt de waarde van d [u] gecontroleerd.

Laten we de pseudo-code bekijken:

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

De pseudocode retourneert de afstand van alle andere knooppunten tot de bron . Als we de afstand van een enkel knooppunt v willen weten, kunnen we eenvoudig de waarde retourneren wanneer v uit de wachtrij wordt gehaald.

Werkt het algoritme van Dijkstra nu er een negatieve kant is? Als er een negatieve cyclus is, zal er een oneindige lus optreden, omdat deze de kosten elke keer blijft verlagen. Zelfs als er een negatieve voorsprong is, zal Dijkstra niet werken, tenzij we terugkeren direct nadat het doelwit is gepopt. Maar dan zal het geen Dijkstra-algoritme zijn. We hebben het Bellman-Ford- algoritme nodig voor het verwerken van negatieve flank / cyclus.

complexiteit:

De complexiteit van BFS is O (log (V + E)) waarbij V het aantal knooppunten is en E het aantal randen is. Voor Dijkstra is de complexiteit vergelijkbaar, maar voor het sorteren van Priority Queue is O (logV) nodig . De totale complexiteit is dus: O (Vlog (V) + E)

Hieronder is een Java-voorbeeld om het kortste padalgoritme van Dijkstra op te lossen met behulp van Adjacency Matrix

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

Verwachte output van het programma is

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