algorithm
Dijkstra's Algorithm

Algoritmo del percorso più breve di Dijkstra

Prima di procedere, è consigliabile avere una breve idea di Adjacency Matrix e BFS

L'algoritmo di Dijkstra è noto come algoritmo di percorso più breve a sorgente singola. Viene utilizzato per trovare i percorsi più brevi tra i nodi in un grafico, che può rappresentare, ad esempio, le reti stradali. Fu ideato da Edsger W. Dijkstra nel 1956 e pubblicato tre anni dopo.

Possiamo trovare il percorso più breve usando l'algoritmo di ricerca di Breadth First Search (BFS). Questo algoritmo funziona bene, ma il problema è che si assume che il costo di attraversare ogni percorso sia lo stesso, il che significa che il costo di ogni spigolo è lo stesso. L'algoritmo di Dijkstra ci aiuta a trovare il percorso più breve in cui il costo di ogni percorso non è lo stesso.

All'inizio vedremo come modificare BFS per scrivere l'algoritmo di Dijkstra, quindi aggiungeremo la coda di priorità per renderlo un algoritmo completo di Dijkstra.

Diciamo che la distanza di ciascun nodo dalla sorgente è mantenuta in array d [] . Come in, d [3] rappresenta che d [3] viene impiegato per raggiungere il nodo 3 dalla sorgente . Se non conosciamo la distanza, memorizzeremo l' infinito in d [3] . Inoltre, lascia che cost [u] [v] rappresenti il ​​costo di uv . Ciò significa che è necessario [u] [v] passare dal nodo u al nodo v .

Dobbiamo capire Edge Relaxation. Diciamo, da casa tua, questa è la fonte , ci vogliono 10 minuti per andare a posizionare A. E ci vogliono 25 minuti per andare al posto B. Abbiamo,

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

Ora diciamo che occorrono 7 minuti per andare dal punto A al punto B , che significa:

cost[A][B] = 7

Quindi possiamo andare a posizionare B dalla sorgente andando a posizionare A dalla sorgente e quindi dal punto A , andando al punto B , che richiederà 10 + 7 = 17 minuti, anziché 25 minuti. Così,

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

Quindi aggiorniamo,

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

Questo è chiamato rilassamento. Andremo dal nodo u al nodo v e se d [u] + costo [u] [v] <d [v] allora aggiorneremo d [v] = d [u] + costo [u] [v] .

In BFS, non avevamo bisogno di visitare alcun nodo due volte. Abbiamo controllato solo se un nodo è visitato o meno. Se non è stato visitato, abbiamo spinto il nodo in coda, contrassegnato come visitato e incrementato la distanza di 1. In Dijkstra, possiamo spingere un nodo in coda e invece di aggiornarlo con visitato, rilassiamo o aggiorniamo il nuovo bordo. Diamo un'occhiata a un esempio:

Supponiamo che il nodo 1 sia la fonte . Poi,

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

Impostiamo, d [2], d [3] e d [4] all'infinito perché non conosciamo ancora la distanza. E la distanza della fonte è ovviamente 0 . Ora, passiamo ad altri nodi dalla fonte e se possiamo aggiornarli, li inseriremo in coda. Ad esempio, attraverseremo il bordo 1-2 . Come d [1] + 2 <d [2] che renderà d [2] = 2 . Allo stesso modo, attraverseremo il bordo 1-3 che rende d [3] = 5 .

Possiamo vedere chiaramente che 5 non è la distanza più breve che possiamo attraversare per andare al nodo 3 . Quindi attraversare un nodo solo una volta, come BFS, non funziona qui. Se passiamo dal nodo 2 al nodo 3 usando il bordo 2-3 , possiamo aggiornare d [3] = d [2] + 1 = 3 . Quindi possiamo vedere che un nodo può essere aggiornato molte volte. Quante volte chiedi? Il numero massimo di volte in cui un nodo può essere aggiornato è il numero di in-degree di un nodo.

Vediamo lo pseudo-codice per visitare più nodi più volte. Modificheremo semplicemente 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

Questo può essere usato per trovare il percorso più breve di tutti i nodi dalla sorgente. La complessità di questo codice non è così buona. Ecco perché,

In BFS, quando passiamo dal nodo 1 a tutti gli altri nodi, seguiamo il metodo first come, first serve . Ad esempio, siamo passati al nodo 3 dalla sorgente prima di elaborare il nodo 2 . Se andiamo al nodo 3 dal sorgente , aggiorniamo il nodo 4 come 5 + 3 = 8 . Quando aggiorniamo nuovamente il nodo 3 dal nodo 2 , dobbiamo aggiornare nuovamente il nodo 4 con 3 + 3 = 6 ! Quindi il nodo 4 viene aggiornato due volte.

Dijkstra ha proposto, invece di usare il metodo Primo arrivato, primo servito , se prima aggiorniamo i nodi più vicini, allora ci vorranno meno aggiornamenti. Se prima avessimo elaborato il nodo 2 , allora il nodo 3 sarebbe stato aggiornato prima, e dopo aver aggiornato il nodo 4 di conseguenza, avremmo ottenuto facilmente la distanza più breve! L'idea è quella di scegliere dalla coda, il nodo, che è più vicino alla fonte . Quindi useremo la Coda prioritaria qui in modo tale che quando salteremo la coda, ci porterà il nodo più vicino u dalla sorgente . Come lo farà? Controllerà il valore di d [u] con esso.

Vediamo lo pseudo-codice:

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

Lo pseudo-codice restituisce la distanza di tutti gli altri nodi dalla sorgente . Se vogliamo conoscere la distanza di un singolo nodo v , possiamo semplicemente restituire il valore quando v viene estratto dalla coda.

Ora, l'Algoritmo di Dijkstra funziona quando c'è un margine negativo? Se c'è un ciclo negativo, allora si verificherà il ciclo infinito, poiché continuerà a ridurre il costo ogni volta. Anche se c'è un vantaggio negativo, Dijkstra non funzionerà, a meno che non torniamo subito dopo che il bersaglio è spuntato. Ma poi, non sarà un algoritmo Dijkstra. Avremo bisogno dell'algoritmo di Bellman-Ford per l'elaborazione del fronte / ciclo negativo.

Complessità:

La complessità di BFS è O (log (V + E)) dove V è il numero di nodi ed E è il numero di spigoli. Per Dijkstra, la complessità è simile, ma l'ordinamento di Priority Queue richiede O (logV) . Quindi la complessità totale è: O (Vlog (V) + E)

Di seguito è riportato un esempio di Java per risolvere l'algoritmo di percorso più breve di Dijkstra usando 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);
    }
}

L'uscita prevista del programma è

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