algorithm
Dijkstra's algoritm

Dijkstra's Shortest Path Algoritm

Innan du fortsätter rekommenderas det att ha en kort uppfattning om Adjacency Matrix och BFS

Dijkstra's algoritm är känd som kortaste sökalgoritm med en källa. Det används för att hitta de kortaste vägarna mellan noderna i en graf, som till exempel kan representera vägnät. Det blev tänkt av Edsger W. Dijkstra 1956 och publicerades tre år senare.

Vi kan hitta den kortaste vägen med hjälp av BFS-sökningsalgoritm. Denna algoritm fungerar bra, men problemet är att det antar att kostnaden för att korsa varje bana är densamma, det betyder att kostnaden för varje kant är densamma. Dijkstra's algoritm hjälper oss att hitta den kortaste vägen där kostnaden för varje väg inte är densamma.

Till att börja med ser vi hur man ändrar BFS för att skriva Dijkstras algoritm, sedan lägger vi till prioriteringskö för att göra det till en komplett Dijkstras algoritm.

Låt oss säga, avståndet för varje nod från källan hålls i d [] -fältet. Som i, representerar d [3] att d [3] tid tar att nå nod 3 från källan . Om vi inte vet avståndet kommer vi att lagra oändlighet i d [3] . Låt också kostnaden [u] [v] representera kostnaden för uv . Det betyder att det tar kostnad [u] [v] att gå från u- nod till v- nod.

Vi måste förstå Edge Relaxation. Låt oss säga, från ditt hus, det är källan , det tar 10 minuter att gå till plats A. Och det tar 25 minuter att gå till plats B. Vi har,

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

Låt oss nu säga att det tar 7 minuter att gå från plats A till plats B , det betyder:

cost[A][B] = 7

Sedan kan vi gå till plats B från källan genom att gå till plats A från källan och sedan från plats A , gå till plats B , vilket tar 10 + 7 = 17 minuter, istället för 25 minuter. Så,

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

Sedan uppdaterar vi,

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

Detta kallas avslappning. Vi går från nod u till nod v och om d [u] + kostar [u] [v] <d [v] så kommer vi att uppdatera d [v] = d [u] + kostnad [u] [v] .

I BFS behövde vi inte besöka någon nod två gånger. Vi kontrollerade bara om en nod är besökt eller inte. Om den inte besökts, tryckte vi noden i kön, markerade den som besökt och ökade avståndet med 1. I Dijkstra kan vi trycka på en nod i kön och istället för att uppdatera den med besökte slappnar vi av eller uppdaterar den nya kanten. Låt oss titta på ett exempel:

Låt oss anta att nod 1 är källan . Sedan,

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

Vi ställer in, d [2], d [3] och d [4] till oändlighet eftersom vi inte vet avståndet ännu. Och källans avstånd är naturligtvis 0 . Nu går vi till andra noder från källan och om vi kan uppdatera dem, kommer vi att trycka dem i kön. Säg till exempel att vi kommer att korsa 1-2 . Som d [1] + 2 <d [2] vilket kommer att göra d [2] = 2 . På liknande sätt kommer vi att korsa kanten 1-3 som gör d [3] = 5 .

Vi kan tydligt se att 5 inte är det kortaste avståndet vi kan korsa för att gå till nod 3 . Så att korsa en nod bara en gång, som BFS, fungerar inte här. Om vi går från nod 2 till nod 3 med kant 2-3 kan vi uppdatera d [3] = d [2] + 1 = 3 . Så vi kan se att en nod kan uppdateras många gånger. Hur många gånger frågar du? Det maximala antalet gånger en nod kan uppdateras är antalet grad av en nod.

Låt oss se pseudokoden för att besöka någon nod flera gånger. Vi kommer helt enkelt att ändra 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

Detta kan användas för att hitta den kortaste sökvägen för alla noder från källan. Komplexiteten hos denna kod är inte så bra. Här är varför,

I BFS, när vi går från nod 1 till alla andra noder, följer vi first come, first serve- metoden. Till exempel gick vi till nod 3 från källan innan vi bearbetar nod 2 . Om vi går till nod 3 från källan uppdaterar vi nod 4 som 5 + 3 = 8 . När vi igen uppdaterar nod 3 från nod 2 , måste vi uppdatera nod 4 som 3 + 3 = 6 igen! Så nod 4 uppdateras två gånger.

Dijkstra föreslog istället för att gå till First come, first serve- metoden, om vi uppdaterar de närmaste noderna först, kommer det att ta mindre uppdateringar. Om vi bearbetade nod 2 tidigare, skulle node 3 ha uppdaterats tidigare, och efter uppdatering av nod 4 i enlighet därmed skulle vi enkelt få det kortaste avståndet! Tanken är att välja från kön, noden, som är närmast källan . Så vi kommer att använda Prioritetskö här så att när vi poppar i kön kommer det att få oss den närmaste nod u från källan . Hur kommer det att göra det? Det kommer att kontrollera värdet på d [u] med det.

Låt oss se pseudokoden:

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

Pseudokoden returnerar avståndet från alla andra noder från källan . Om vi vill veta avståndet för en enda nod v , kan vi helt enkelt returnera värdet när v poppas från kön.

Nu fungerar Dijkstra's algoritm när det finns en negativ kant? Om det finns en negativ cykel, kommer infinity loop att inträffa, eftersom det fortsätter att sänka kostnaden varje gång. Även om det finns en negativ kant, fungerar Dijkstra inte, såvida vi inte återvänder direkt efter att målet har dykt upp. Men då kommer det inte att vara en Dijkstra-algoritm. Vi behöver Bellman – Ford algoritm för att bearbeta negativ kant / cykel.

Komplexitet:

Komplexiteten hos BFS är O (log (V + E)) där V är antalet noder och E är antalet kanter. För Dijkstra är komplexiteten liknande, men sortering av Prioritetskö tar O (logV) . Så den totala komplexiteten är: O (Vlog (V) + E)

Nedan är ett Java-exempel för att lösa Dijkstra's Shortest Path Algoritm med hjälp av 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);
    }
}

Förväntat resultat från programmet är

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