algorithm
Dijkstra-Algorithmus

Dijkstra's Kürzester Pfad-Algorithmus

Bevor Sie fortfahren, wird empfohlen, sich kurz über Adjacency Matrix und BFS zu informieren

Der Algorithmus von Dijkstra ist als Algorithmus für den kürzesten Weg mit einer Quelle bekannt. Sie wird zum Finden der kürzesten Pfade zwischen Knoten in einem Graphen verwendet, die zum Beispiel Straßennetze darstellen können. Es wurde 1956 von Edsger W. Dijkstra konzipiert und drei Jahre später veröffentlicht.

Wir können den kürzesten Weg mithilfe des Suchalgorithmus Breadth First Search (BFS) finden. Dieser Algorithmus funktioniert gut, aber das Problem besteht darin, dass die Kosten für das Durchlaufen der einzelnen Pfade gleich sind. Dies bedeutet, dass die Kosten für jede Kante gleich sind. Der Algorithmus von Dijkstra hilft uns, den kürzesten Weg zu finden, bei dem die Kosten für jeden Weg nicht gleich sind.

Zuerst werden wir sehen, wie man BFS modifiziert, um den Algorithmus von Dijkstra zu schreiben, und dann werden wir die Prioritätswarteschlange hinzufügen, um daraus einen vollständigen Dijkstra-Algorithmus zu machen.

Sagen wir, der Abstand jedes Knotens von der Quelle wird in d [] -Array gehalten. Wie in, stellt d [3] dar, dass die Zeit d [3] benötigt wird, um den Knoten 3 von der Quelle zu erreichen. Wenn wir die Entfernung nicht kennen, speichern wir unendlich in d [3] . Lassen Sie auch die Kosten [u] [v] die Kosten von UV darstellen . Das bedeutet, dass die Kosten [u] [v] vom u- Knoten zum v- Knoten gehen.

Wir müssen Edge Relaxation verstehen. Nehmen wir an, aus Ihrem Haus, das ist die Quelle , dauert es 10 Minuten, um Platz A zu erreichen . Und es dauert 25 Minuten, um Platz B zu erreichen . Wir haben,

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

Nehmen wir an, es dauert 7 Minuten, um von Ort A zu Ort B zu gelangen . Das bedeutet:

cost[A][B] = 7

Dann können wir gehen B von der Quelle zu platzieren , indem Sie einen von der Quelle platzieren und dann von Ort A, B zu platzieren gehen, die 10 nehmen + 7 = 17 Minuten statt 25 Minuten. So,

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

Dann aktualisieren wir

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

Das nennt man Entspannung. Wir gehen vom Knoten u zum Knoten v und wenn d [u] + cost [u] [v] <d [v] ist, werden wir d [v] = d [u] + cost [u] [v] aktualisieren.

In BFS mussten wir keinen Knoten zweimal besuchen. Wir haben nur geprüft, ob ein Knoten besucht wird oder nicht. Wenn es nicht besucht wurde, haben wir den Knoten in die Warteschlange gestellt, als besucht markiert und die Entfernung um 1 erhöht. In Dijkstra können wir einen Knoten in die Warteschlange stellen und anstatt ihn mit besucht zu aktualisieren, lockern oder aktualisieren wir die neue Kante. Schauen wir uns ein Beispiel an:

Nehmen wir an, Knoten 1 ist die Quelle . Dann,

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

Wir setzen d [2], d [3] und d [4] auf unendlich, weil wir die Entfernung noch nicht kennen. Und die Entfernung der Quelle ist natürlich 0 . Nun gehen wir von Quelle zu anderen Knoten und wenn wir sie aktualisieren können, dann schieben wir sie in die Warteschlange. Sagen wir zum Beispiel, wir werden die Kante 1-2 überqueren. Als d [1] + 2 <d [2] wird d [2] = 2 . In ähnlicher Weise werden wir die Kante 1-3 überqueren, wodurch d [3] = 5 wird .

Wir können deutlich erkennen, dass 5 nicht die kürzeste Entfernung ist, die wir überqueren können, um zum Knoten 3 zu gelangen . Ein Knoten nur einmal zu durchlaufen, wie BFS, funktioniert hier nicht. Wenn wir mit der Kante 2-3 vom Knoten 2 zum Knoten 3 gehen, können wir d [3] = d [2] + 1 = 3 aktualisieren. Wir können also sehen, dass ein Knoten viele Male aktualisiert werden kann. Wie oft fragst du? Die maximale Anzahl von Malen, die ein Knoten aktualisiert werden kann, ist die Anzahl der Gradienten eines Knotens.

Sehen wir uns den Pseudo-Code an, um einen Knoten mehrfach zu besuchen. Wir werden BFS einfach modifizieren:

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

Dies kann verwendet werden, um den kürzesten Pfad aller Knoten von der Quelle zu finden. Die Komplexität dieses Codes ist nicht so gut. Hier ist der Grund,

Wenn wir in BFS von Knoten 1 zu allen anderen Knoten wechseln, folgen wir der First-First-First-Serving- Methode. Zum Beispiel sind wir vor der Verarbeitung von Knoten 2 von Quelle zu Knoten 3 gegangen. Wenn wir von Quelle zu Knoten 3 gehen, aktualisieren wir Knoten 4 mit 5 + 3 = 8 . Wenn wir Knoten 3 erneut von Knoten 2 aktualisieren, müssen wir Knoten 4 erneut mit 3 + 3 = 6 aktualisieren! Knoten 4 wird also zweimal aktualisiert.

Dijkstra schlug vor, die First-First-First-Served- Methode zu verwenden, wenn zuerst die nächstgelegenen Knoten aktualisiert werden, sind dann weniger Updates erforderlich. Wenn wir Knoten 2 vorher bearbeitet hätten, wäre Knoten 3 zuvor aktualisiert worden, und nachdem Knoten 4 entsprechend aktualisiert wurde, würde man leicht die kürzeste Entfernung erhalten! Die Idee ist, aus der Warteschlange den Knoten auszuwählen, der der Quelle am nächsten liegt. Daher werden wir hier die Prioritätswarteschlange verwenden , so dass wir, wenn wir die Warteschlange öffnen, den nächstgelegenen Knoten u von der Quelle erhalten . Wie wird es das machen? Damit wird der Wert von d [u] überprüft.

Schauen wir uns den Pseudo-Code an:

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

Der Pseudocode gibt die Entfernung aller anderen Knoten von der Quelle zurück . Wenn wir die Entfernung eines einzelnen Knotens v erfahren möchten, können wir den Wert einfach zurückgeben, wenn v aus der Warteschlange herausgezogen wird.

Funktioniert der Dijkstra-Algorithmus jetzt, wenn es eine negative Flanke gibt? Wenn es einen negativen Zyklus gibt, tritt eine Unendlichkeitsschleife auf, da dies die Kosten jedes Mal verringert. Auch wenn eine negative Flanke vorliegt, funktioniert Dijkstra nicht, es sei denn, wir kehren direkt nach dem Abspringen des Ziels zurück. Aber es wird kein Dijkstra-Algorithmus sein. Wir benötigen den Bellman-Ford- Algorithmus für die Verarbeitung von negativen Kanten / Zyklus.

Komplexität:

Die Komplexität von BFS ist O (log (V + E)), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist. Für Dijkstra ist die Komplexität ähnlich, aber das Sortieren der Prioritätswarteschlange erfordert O (logV) . Die Gesamtkomplexität ist also: O (Vlog (V) + E)

Nachfolgend finden Sie ein Java-Beispiel, um den Shortest Path-Algorithmus von Dijkstra mithilfe der Adjacency-Matrix zu lösen

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

Erwartete Ausgabe des Programms ist

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