Dijkstras Algorithmus in Python

Der Algorithmus von Dijkstra kann als gieriger Algorithmus definiert werden, der verwendet werden kann, um die kürzest mögliche Entfernung von einem Quellknoten zu jedem anderen möglichen Knoten, der in einem gewichteten Graphen existiert, herauszufinden, vorausgesetzt, der Knoten ist vom Quellknoten aus erreichbar.

In diesem Tutorial wird erläutert, wie Sie den Dijkstra-Algorithmus zum Finden des kürzesten Pfads in Python implementieren.

Wie oben erwähnt, ist der Algorithmus von Dijkstra gierig. Ein gieriger Algorithmus kann als ein algorithmisches Paradigma definiert werden, das sich darauf konzentriert, eine Stück für Stück Lösung für das gegebene Problem aufzubauen und dann die günstigste Option auszuwählen.

Der Algorithmus von Dijkstra funktioniert wie folgt.

• Wählen Sie bei einigen nicht besuchten Scheitelpunkten den Scheitelpunkt mit der kleinsten Entfernung von der Quelle aus und besuchen Sie ihn.
• Die Entfernung für jeden Nachbarn wird dann aktualisiert. Das gleiche wird für den besuchten Scheitelpunkt gemacht, der einen aktuellen Abstand größer als die Summe und das Gewicht der gegebenen Kante zwischen ihnen hat.
• Die Schritte 1 und 2 müssen wiederholt werden, bis keine nicht besuchten Scheitelpunkte mehr vorhanden sind.

Der Algorithmus von Dijkstra ähnelt dem Minimum Spanning Tree-Algorithmus von Prim, einem weiteren Greedy-Algorithmus, da beide die Erzeugung eines SPT (Shortest Path Tree) benötigen, wobei die Quelle als Wurzel des Baums verwendet wird.

Der folgende Code verwendet den Dijkstra-Algorithmus, um den kürzesten Pfad in Python zu finden.

import sys


class Graph:
    def __init__(self, vertx):
        self.V = vertx
        self.graph = [[0 for column in range(vertx)] for row in range(vertx)]

    def pSol(self, dist):
        print("Distance of vertex from source")
        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijk(self, source):

        dist = [sys.maxsize] * self.V
        dist[source] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            u = self.minDistance(dist, sptSet)

            sptSet[u] = True

            for v in range(self.V):
                if (
                    self.graph[u][v] > 0
                    and sptSet[v] == False
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.pSol(dist)


f = Graph(9)
f.graph = [
    [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],
]

f.dijk(0)

Der obige Code liefert die folgende Ausgabe:

Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

Der Algorithmus von Dijkstra ist dem Algorithmus der Tiefensuche sehr ähnlich, obwohl diese beiden Algorithmen nicht genau für denselben Zweck existieren.

Der einzige signifikante Unterschied zwischen der Tiefensuche und dem Dijkstra-Algorithmus besteht darin, dass ersterer langsamer arbeitet als letzterer, da der Tiefensuche(DFS)-Algorithmus die Stapeltechnik verwendet. Andererseits verwendet der Algorithmus von Dijkstra die vergleichsweise langsamere Heap-Technik.