TL;DR

Lernen Sie die Dyxtra-Methode kennen, um die kürzeste Route des Diagramms zu berechnen. ――Wir werden auch auf die grundlegenden Begriffe eingehen, die in der Graphentheorie verwendet werden. ―― Schreiben Sie die Dyxtra-Methode tatsächlich in Python, um Ihr Verständnis zu vertiefen.

Erklärung der Grafiken und einfachen Begriffe, auf die diesmal abgezielt wurde

Dieses Mal werden wir uns mit den folgenden Grafiken befassen. Stellen Sie sich so etwas wie eine Stationsroutenkarte vor.

ダイクストラ法_1.png

Teile wie A und B werden als Scheitelpunkt oder Knoten bezeichnet. In Bezug auf die Streckenkarte wird es eine Haltestelle sein.

Der Teil der Linie, der jeden Scheitelpunkt verbindet, wird als Kante oder Kante / Zweig bezeichnet. In Bezug auf die Streckenkarte entspricht sie den Linienverbindungsstationen.

Die Zahlen an den Kanten werden als Gewichte und Kosten bezeichnet. Es sind die Kosten, die erforderlich sind, um diese Kante zu passieren. In Bezug auf die Streckenkarte entspricht sie der Entfernung zwischen den Stationen. In diesem Artikel werden wir uns mit dem Abstand zwischen Eckpunkten befassen.

Darüber hinaus gibt es zwei Arten von Diagrammen: ungerichtete Diagramme und gerichtete Diagramme. Die Richtung des ungerichteten Graphen ist zwischen den Eckpunkten nicht festgelegt. Sie können in beide Richtungen gehen. Apropos Streckenkarte: Es ist, als würde man an einer bestimmten Station auf und ab gehen. Auf der anderen Seite können gerichtete Graphen nur in eine Richtung zwischen Scheitelpunkten vorrücken. Dieser Artikel befasst sich mit dem Inhalt ungerichteter Diagramme.

Was ist die Dyxtra-Methode?

Dijkstra's Algorithm Der Dijkstra-Algorithmus ist ein graphentheoretischer Algorithmus zur Berechnung des kürzesten Weges eines Graphen.

Der Algorithmus berechnet, wie von einem bestimmten Scheitelpunkt zum anderen gewechselt werden kann, um die kürzeste Entfernung zu erhalten.

Der Inhalt ähnelt dem A \ * -Algorithmus, der in dem Artikel erwähnt wurde, den ich vor einiger Zeit geschrieben habe ([Schreiben des A \ * -Algorithmus (A-Stern) in Python) (https://qiita.com/simonritchie/items/5e31c5cb7c885c9b814a)). (Obwohl es Unterschiede wie Heuristiken gibt).

Das Problem, das diesmal mit Python gelöst werden muss

Berechnen Sie den kürzesten Pfad von Scheitelpunkt A zu Scheitelpunkt J in Python in der folgenden Grafik, die ich vor einiger Zeit erwähnt habe.

Berechnungsinhalt der Dyxtra-Methode

[1] Bestimmen Sie den Startpunkt.
[2]. Speichert den Abstand vom Startscheitelpunkt zum Scheitelpunkt neben diesem Scheitelpunkt in einer Liste oder dergleichen. -Es enthält auch einen Verweis auf die Kante, die zu den benachbarten Eckpunkten führte.
[3] Gehen Sie als Nächstes zum benachbarten Scheitelpunkt und speichern Sie den Abstand vom Startscheitelpunkt zum Scheitelpunkt neben diesem Scheitelpunkt.
Wenn zu diesem Zeitpunkt die Entfernung vom Startscheitelpunkt des benachbarten Scheitelpunkts bereits gespeichert ist (wenn die Entfernung zum Zielscheitelpunkt auf einer anderen Route berechnet wird), wird sie nur gespeichert, wenn die Entfernung kurz wird. Aktualisieren Sie den Wert der Entfernung, die Sie sind. --Wenn der Abstand aktualisiert wird, wird auch die Referenz der Kante auf den in [2] enthaltenen Scheitelpunkt aktualisiert. -Wiederholen Sie [4]. [3] und wiederholen Sie die Berechnung, bis keine Ziele mehr vorhanden sind (die Berechnung aller Routen ist abgeschlossen).

Wenn Sie nach Abschluss der Berechnung den kürzesten Abstand vom Startscheitelpunkt zu einem Scheitelpunkt erhalten möchten, behält jeder Scheitelpunkt die Referenz der Kante unmittelbar vor dem kürzesten, der diesen Scheitelpunkt erreicht, also das endgültige Sie können die kürzeste Route ermitteln, indem Sie sich auf die Kante in der Reihenfolge vom oberen Ende des Ziels beziehen, zum oberen Rand des Starts zurückkehren und die Route umkehren.

Es ist schwer zu verstehen, ob es nur Buchstaben sind, also werde ich es mit einer kleinen Figur berühren. Erstens sind die Teile [1] und [2].

ダイクストラ法_3.png

Der Teil in Rot ist der Abstand, der durch die Berechnungsiteration berechnet wird. Zuerst beginnen wir oben in A.

Es ist natürlich von der Spitze von A bis zur Spitze von A, aber der Abstand ist 0. Halten Sie den Abstand und die Kante zu diesem Scheitelpunkt an den in [2] erforderlichen Eckpunkten von B und E neben A.

Zu diesem Zeitpunkt wurde der Abstand zwischen den Eckpunkten des Ziels B und E nicht auf anderen Wegen berechnet, sodass dieser Wert unverändert bleibt. Zu diesem Zeitpunkt beträgt der kürzeste Abstand zum Scheitelpunkt von B 80 und der kürzeste Abstand zum Scheitelpunkt von E 200.

Es speichert auch die Informationen der Kante unmittelbar vor dem kürzesten Abstand (diesmal die Kante zwischen A und B und die Kante zwischen A und E).

Bewegen Sie als nächstes bei der Berechnung von [3] das Ziel zum Scheitelpunkt von B. Da vier Eckpunkte A, C, D und E neben den Eckpunkten von B liegen, werden für jeden Eckpunkt Berechnungen durchgeführt.

Zuallererst die Entfernung von B nach A, die berechnet wird, um auf der Route zurückzukehren. Ursprünglich wurde der Abstand von A nach A auf 0 gesetzt, sodass die Route A → B → A einen Abstand von 80 + 80 hat, was 160 entspricht. Da dieser Abstand größer als 0 ist, werden die Abstands- oder Kantenreferenzen nicht aktualisiert.

In ähnlicher Weise beträgt die Entfernung für die Route von B nach E 290, was bereits größer ist als die Entfernung von 200 für die Route von A nach E, sodass die kürzesten Entfernungs- und Kantenreferenzen nicht aktualisiert werden.

Da die Entfernung von B nach C und von B nach D noch nicht von einer anderen Route berechnet wurde, wird sie neu übernommen und als kürzeste Entfernung beibehalten.

Wenn die Berechnung des Scheitelpunkts von B in Schritt [3] abgeschlossen ist, ist dies wie folgt.

ダイクストラ法_4.png

Auf diese Weise wird der Zielscheitelpunkt in der Reihenfolge verschoben und die Aktualisierung wird wiederholt, wenn der Abstand zum benachbarten Scheitelpunkt noch nicht berechnet wurde oder der kürzeste Abstand kürzer wird. Die aktualisierten benachbarten Scheitelpunkte werden später als Zielscheitelpunkte für die Berechnung zur Warteschlange hinzugefügt.

Was ist in der Python-Implementierung zu verwenden?

Python 3.8.5

Implementierung in Python

Importieren Sie zunächst die erforderlichen Module. Da Typanmerkungen verwendet werden, fügen Sie Anmerkungen und jede Klasse des Typisierungspakets hinzu. Da ich eine Prioritätswarteschlange verwende, um die Scheitelpunkte zu steuern, auf die bei der Berechnung der Dyxtra-Methode abgezielt werden soll (ich habe das Gefühl, dass ich eine normale Warteschlange verwenden kann, ohne sie zu verwenden), lade ich die in das Heapq-Paket. ..

from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop

Als nächstes definieren wir Konstanten für die Eckpunkte. VertexStr ist ein einfacher Str-Alias. Wenn Sie es missbrauchen, kann es schwierig sein, es von der Klasse zu unterscheiden, aber es ist bequem zu verstehen, dass "dieses Argument eine Folge von Konstanten an den Eckpunkten ist", daher werde ich es dieses Mal verwenden.

VertexStr = str


class Vertex:
    """Eine Klasse, die Konstanten von Zeichenfolgen verarbeitet, die jeden Scheitelpunkt darstellen.
    """

    A: VertexStr = 'A'
    B: VertexStr = 'B'
    C: VertexStr = 'C'
    D: VertexStr = 'D'
    E: VertexStr = 'E'
    F: VertexStr = 'F'
    G: VertexStr = 'G'
    H: VertexStr = 'H'
    I: VertexStr = 'I'
    J: VertexStr = 'J'
    K: VertexStr = 'K'

Als nächstes definieren wir eine Klasse für die Kante. Enthält die Scheitelpunktinformationen und das Gewicht an dieser Kante (in diesem Fall den Abstand) im Attribut (um zu bestimmen, mit welchem Scheitelpunkt die Kante verbunden werden soll).

class Edge:

    def __init__(
            self, from_idx: int, to_idx: int,
            from_vertex: VertexStr, to_vertex: VertexStr,
            weight: float) -> None:
        """
Eine Klasse, die eine einzelne Kante behandelt.

        Parameters
        ----------
        from_idx : int
Index des Verbindungsquellenscheitelpunkts.
        to_idx : int
Index des verbundenen Scheitelpunkts.
        weight : float
Kantengewicht.
        """
        self.from_idx: int = from_idx
        self.to_idx: int = to_idx
        self.from_vertex: VertexStr = from_vertex
        self.to_vertex: VertexStr = to_vertex
        self.weight: float = weight

Fügen Sie im Kantenadditionsprozess eine Methode zur Inversion hinzu, da es zweckmäßig ist, die Methode hinzuzufügen, deren Richtung invertiert ist (generieren Sie beispielsweise die Kante von Scheitelpunkt B → Scheitelpunkt A aus der Kante von Scheitelpunkt A → Scheitelpunkt B).

    def reversed(self) -> Edge:
        """
Holen Sie sich die Kante mit der Verbindungsquelle und dem Ziel der Scheitelpunkte invertiert.

        Returns
        -------
        reversed_edge : Edge
Eine Kante, bei der die Verbindungsquelle und das Ziel der Scheitelpunkte invertiert sind.
        """
        reversed_edge = Edge(
            from_idx=self.to_idx,
            to_idx=self.from_idx,
            from_vertex=self.from_vertex,
            to_vertex=self.to_vertex,
            weight=self.weight)
        return reversed_edge

Passen Sie außerdem den Inhalt an, wenn die Instanz dieser Klasse von der Druckfunktion usw. ausgegeben wird, damit Sie die Route später bequem ausgeben können. Die Ausgabe wird wie folgt sein.

from: A(weight: 80) -> to: B

    def __str__(self) -> str:
        """
Konvertieren Sie Kanteninformationen in eine Zeichenfolge.

        Returns
        -------
        edge_info_str : str
Eine Zeichenfolge konvertierter Kanteninformationen.
        """
        edge_info_str: str = (
            f'from: {self.from_vertex}'
            f'(weight: {self.weight})'
            f' -> to: {self.to_vertex}'
        )
        return edge_info_str

Als nächstes definieren wir eine Klasse für das Diagramm. Geben Sie für die Argumentscheitelpunkte später eine Liste der Werte der Vertex-Klassenkonstanten an, z. B. "A", "B", "C" ...

Eine mehrdimensionale Liste wird erstellt, indem so oft wiederholt wird, wie das Attribut "_edges" Scheitelpunkte enthält. In der zweiten Dimension werden mehrere Kanten gespeichert, die mit dem Zielscheitelpunkt verbunden sind. Die Kanten sind zu diesem Zeitpunkt noch leer, aber wir werden sie später hinzufügen.

class Graph:

    def __init__(self, vertices: List[VertexStr]) -> None:
        """
Eine Klasse zum Arbeiten mit Grafiken.

        Parameters
        ----------
        vertices : list of str
Eine Liste von Eckpunktfolgen.
        """
        self._vertices: List[VertexStr] = vertices
        self._edges: List[List[Edge]] = []
        for _ in vertices:
            self._edges.append([])

Wir werden jede für einige Berechnungen erforderliche Methode hinzufügen. Die erste ist die Methode, um die Eckpunkte der Zielindexposition zu erhalten.

    def vertex_at(self, index: int) -> VertexStr:
        """
Ruft die Zeichenfolge der Scheitelpunkte des angegebenen Index ab.

        Parameters
        ----------
        index : int
Zielindex.

        Returns
        -------
        vertex_str : str
Eine Folge von Eckpunkten an der Zielindexposition.
        """
        return self._vertices[index]

Fügen Sie umgekehrt eine Methode hinzu, um den entsprechenden Index aus der Zeichenfolge der Scheitelpunkte abzurufen.

    def index_of(self, vertex: VertexStr) -> int:
        """
Holen Sie sich den Intex des Zielscheitelpunkts.

        Parameters
        ----------
        vertex : str
Eine Zeichenfolge zur Identifizierung des Zielscheitelpunkts.

        Returns
        -------
        index : int
Index des Zielscheitelpunkts.
        """
        return self._vertices.index(vertex)

Fügen Sie eine Methode als Eigenschaft für die Anzahl der Scheitelpunkte hinzu.

    @property
    def vertex_count(self):
        """
Attributwert der festgelegten Anzahl von Eckpunkten.

        Returns
        -------
        vertex_count : int
Die Anzahl der Scheitelpunkte, die festgelegt wurden.
        """
        return len(self._vertices)

Fügen Sie eine Methode hinzu, um eine Liste der Kanten zu erhalten, die mit den Eckpunkten der Zielindexposition verbunden sind.

    def edges_at(self, vertex_index: int) -> List[Edge]:
        """
Von der am Scheitelpunkt der angegebenen Indexposition eingestellten Kante
Holen Sie sich die Liste.

        Parameters
        ----------
        vertex_index : int
Index der Zielscheitelpunktposition.

        Returns
        -------
        edges : list of Edge
Eine Liste der Kanten, die für den Zielscheitelpunkt festgelegt wurden.
        """
        return self._edges[vertex_index]

Fügt einen Prozess hinzu, um eine Liste von Tupeln zu erhalten, in denen die Gewichte der Kanten neben dem angegebenen Scheitelpunkt gespeichert sind. Es wird in der Berechnung verwendet, um die benachbarten Scheitelpunkte zu berechnen, wenn der kürzeste Abstand für einen bestimmten Scheitelpunkt berechnet wird.

    def get_neighbor_vertices_and_weights_by_index(
            self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
        """
Verbunden mit den Eckpunkten des angegebenen Index mit einer Kante
Rufen Sie eine Liste mit Tupeln mit Gewichtswerten für einen Scheitelpunkt und seine Kanten ab.

        Parameters
        ----------
        vertex_index : int
Index des Zielscheitelpunkts.

        Returns
        -------
        neighbor_vertices_and_weights : list of tuple
Eine Liste mit Tapples berechneter Eckpunkte und deren Kantengewichten.
        """
        neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
        for edge in self.edges_at(vertex_index=vertex_index):
            tuple_val = (
                self.vertex_at(index=edge.to_idx),
                edge.weight,
            )
            neighbor_vertices_and_weights.append(tuple_val)
        return neighbor_vertices_and_weights

Fügen Sie eine Methode hinzu, um dem Diagramm Kanten hinzuzufügen. Wir möchten auch Kanten in die entgegengesetzte Richtung hinzufügen, um die Beschreibung zu reduzieren. Wenn beispielsweise eine Kante in Richtung A → B hinzugefügt wird, sollte auch eine Kante in Richtung B → A hinzugefügt werden. Verwenden Sie zum Generieren einer gespiegelten Kante die umgekehrte Methode, die der Kantenklasse hinzugefügt wurde.

    def add_edge(self, edge: Edge) -> None:
        """
Fügen Sie dem Diagramm Kanten hinzu.

        Notes
        -----
Zu den verbundenen Scheitelpunkten werden auch umgekehrte Kanten hinzugefügt (Kanten sind
Durch Ausführen der Methode werden insgesamt 2 Elemente hinzugefügt.

        Parameters
        ----------
        edge : Edge
Die hinzuzufügende Kante.
        """
        self._edges[edge.from_idx].append(edge)
        self._edges[edge.to_idx].append(edge.reversed())

Außerdem wird eine Methode hinzugefügt, die dann Kanten entsprechend den Zeichen an den beiden angegebenen Scheitelpunkten hinzufügt. Auf diese Weise können Sie so etwas wie "eine Kante zwischen A und B hinzufügen" schreiben. Da die Methode add_edge intern aufgerufen wird, wird auch die Kante in der entgegengesetzten Richtung hinzugefügt (in umgekehrter Form).

Am Ende der Diagrammklasse sollten die Informationen der zum Zeitpunkt des Druckens hinzugefügten Scheitelpunkte usw. und der für diese Scheitelpunkte festgelegten benachbarten Scheitelpunkte (und Kanten) ausgegeben werden. Die Ausgabe wird wie folgt sein.

Diagramminformationen:
Zielscheitelpunkte: A ->Benachbarte Scheitelpunktdaten: [('B', 80), ('E', 200)]
Zielscheitelpunkte: B ->Benachbarte Scheitelpunktdaten: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
...

    def __str__(self) -> str:
        """
Gibt die Zeichenfolge der Diagramminformationen zurück.

        Returns
        -------
        graph_info : str
Eine Zeichenfolge mit Diagramminformationen.
        """
        graph_info: str = ''
        for index in range(self.vertex_count):
            neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
                vertex_index=index)
            graph_info += (
                f'Zielscheitelpunkte: {self.vertex_at(index=index)}'
                f' ->Benachbarte Scheitelpunktdaten: {neighbors_data}\n'
            )
        return graph_info

Fügen Sie als Nächstes eine Klasse hinzu, die den Abstand vom Startscheitelpunkt zu einem bestimmten Scheitelpunkt nach der Dyxtra-Methode behandelt und die Verarbeitung zur Berechnung des Gewichts (Abstand) beschreibt.

class DijkstraDistanceVertex:

    def __init__(self, vertex_idx: int, distance: float) -> None:
        """
Abstand (Gewicht) vom Beginn eines bestimmten Scheitelpunkts für die Dyxtra-Methode
Eine Klasse zur Vergleichskontrolle mit anderen Eckpunkten.

        Parameters
        ----------
        vertex : str
Index zur Identifizierung des Zielscheitelpunkts.
        distance : float
Abstand von der Spitze des Starts.
        """
        self.vertex_idx = vertex_idx
        self.distance = distance

Fügen Sie eine Methode zum Gewichtsvergleich hinzu. Mit der Dyxtra-Methode wird bestimmt, ob die Route zu einem bereits berechneten Scheitelpunkt nach der Berechnung verkürzt wird.

    def __lt__(self, other: DijkstraDistanceVertex) -> bool:
        """
Erfasst den Wahrheitswert des Vergleichsergebnisses der Entfernung (Gewicht) anderer Eckpunkte.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Der zu vergleichende Scheitelpunkt.

        Returns
        -------
        result : bool
Wenn True und die geringere Bedingung erfüllt ist.
        """
        return self.distance < other.distance

    def __eq__(self, other: DijkstraDistanceVertex) -> bool:
        """
Boolescher Wert, ob der Abstand (Gewicht) mit anderen Scheitelpunkten übereinstimmt
erhalten.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Der zu vergleichende Scheitelpunkt.

        Returns
        -------
        result : bool
Wenn True und die Übereinstimmungsbedingung erfüllt ist.
        """
        return self.distance == other.distance

Als nächstes wird die Prioritätswarteschlangenklasse vorbereitet. Jedes Mal, wenn der kürzeste Abstand zu jedem Scheitelpunkt aktualisiert wird, wird dieser Scheitelpunkt zur Warteschlange hinzugefügt. Immerhin wird es für alle berechnet, also war es in Ordnung, eine normale Warteschlange zu verwenden, auch wenn sie nicht priorisiert wurde ...? Ich habe keine Lust dazu.

class PriorityQueue:

    def __init__(self) -> None:
        """
Eine Klasse, die Prioritätswarteschlangen verarbeitet.
        """
        self._container: List[DijkstraDistanceVertex] = []

    @property
    def empty(self) -> bool:
        """
Boolesches Attribut, ob die Warteschlange leer ist.

        Returns
        -------
        result : bool
True wird gesetzt, wenn die Warteschlange leer ist.
        """
        return not self._container

    def push(self, item: DijkstraDistanceVertex) -> None:
        """
Behandeln Sie den Abstand vom Beginn eines bestimmten Scheitelpunkts der Dyxtra-Methode zur Warteschlange
Fügen Sie eine Instanz hinzu.

        Parameters
        ----------
        item : DijkstraDistanceVertex
Die hinzuzufügende Instanz.
        """
        heappush(self._container, item)

    def pop(self) -> DijkstraDistanceVertex:
        """
Extrahieren Sie eine Instanz entsprechend der Priorität aus der Warteschlange.

        Returns
        -------
        item : DijkstraDistanceVertex
Die abgerufene Instanz.
        """
        return heappop(self._container)

Nachdem wir alle Diagramme fertig haben, schreiben wir die Berechnungen der Dyxtra-Methode.

def dijkstra(
        graph: Graph,
        root_vertex: VertexStr
        ) -> tuple[List[Optional[float]], Dict[int, Edge]]:
    """
Führen Sie die Dikstra-Methode, den Abstand für jeden Scheitelpunkt und den kürzesten Weg zu jedem Scheitelpunkt aus
Berechnen Sie den Pfad.

    Parameters
    ----------
    graph : Graph
Zieldiagramm.
    root_vertex : str
Eine Zeichenfolge zum Identifizieren des Scheitelpunkts an der Position, an der die Suche gestartet wird.

    Returns
    -------
    distances : list of float
Der Abstand von der Spitze der Suchstartposition jedes Scheitelpunkts.
    path_dict : dict
Der Schlüssel ist der Index des Zielscheitelpunkts, und der Wert ist der Index des Zielscheitelpunkts.
Speichert die unmittelbar vorhergehende Kante der kürzesten Route.
    """
    first_idx: int = graph.index_of(vertex=root_vertex)
    distances: List[Optional[float]] = [
        None for _ in range(graph.vertex_count)]
    distances[first_idx] = 0

    path_dict: Dict[int, Edge] = {}
    priority_queue: PriorityQueue = PriorityQueue()
    priority_queue.push(
        item=DijkstraDistanceVertex(
            vertex_idx=first_idx,
            distance=0))

    while not priority_queue.empty:
        from_idx:int = priority_queue.pop().vertex_idx
        from_vertex_distance: float = distances[from_idx]
        for edge in graph.edges_at(vertex_index=from_idx):

            #Bereits vor der Zieliteration auf den Zielscheitelpunkt gesetzt
            #Holen Sie sich die Entfernung (Wert, der durch eine andere Route festgelegt wurde usw.).
            to_distance: Optional[float] = distances[edge.to_idx]

            #Berechnen Sie die Entfernung auf dieser Route.
            current_route_distance: float = edge.weight + from_vertex_distance

            #Wenn die Entfernung auf einer anderen Route bereits eingestellt wurde und auf dieser Route
            #Wenn die Entfernung nicht kürzer ist, wird der Aktualisierungsvorgang übersprungen.
            if (to_distance is not None
                    and to_distance <= current_route_distance):
                continue

            distances[edge.to_idx] = current_route_distance
            path_dict[edge.to_idx] = edge
            priority_queue.push(
                item=DijkstraDistanceVertex(
                    vertex_idx=edge.to_idx,
                    distance=current_route_distance))

    return distances, path_dict

Für das Argument root_vertex möchten wir diesmal den kürzesten Weg von A nach J ermitteln. Geben Sie daher A später an.

    while not priority_queue.empty:

Und so weiter wird der Prozess mit der while-Anweisung fortgesetzt, bis der zu durchsuchende Scheitelpunkt aus der Warteschlange verschwindet.

            to_distance: Optional[float] = distances[edge.to_idx]

In der while-Anweisung wird der vergangene Wert (Wert, der bereits von einer anderen Route berechnet wurde) für die Entfernung zum Berechnungszielscheitelpunkt erfasst. Zuerst ist Keine eingestellt. Wenn es sich also um den ersten Peak handelt, ist es Keine.

            current_route_distance: float = edge.weight + from_vertex_distance

Berechnet den aktuellen Abstand der while-Anweisung. Das Gewicht (Abstand) der unmittelbar vorhergehenden Kante und der Abstand zum unmittelbar vorhergehenden Scheitelpunkt werden addiert.

            if (to_distance is not None
                    and to_distance <= current_route_distance):
                continue

Wenn die von einer anderen Route berechnete Entfernung bereits vorhanden ist und die durch diese Iteration berechnete Entfernung nicht kürzer wird, ist eine Aktualisierung nicht erforderlich und der Vorgang wird übersprungen.

            distances[edge.to_idx] = current_route_distance
            path_dict[edge.to_idx] = edge
            priority_queue.push(
                item=DijkstraDistanceVertex(
                    vertex_idx=edge.to_idx,
                    distance=current_route_distance))

Wenn der Abstand verkürzt wird oder wenn es sich um den ersten zu berechnenden Scheitelpunkt handelt, aktualisieren Sie den Abstand zu diesem Scheitelpunkt, aktualisieren Sie die Informationen der Kante unmittelbar vor dem kürzesten Abstand zu diesem Scheitelpunkt und berechnen Sie diesen Scheitelpunkt in einer späteren Iteration. Zur Warteschlange hinzufügen.

    return distances, path_dict

Der Rückgabewert ist eine Liste, in der Informationen zur kürzesten Entfernung zu jedem Scheitelpunkt gespeichert sind, und ein Wörterbuch, in dem die Kante unmittelbar vor der Route gespeichert ist, die die kürzeste Entfernung zu jedem Scheitelpunkt darstellt.

Bereiten Sie als Nächstes eine Funktion vor, um den kürzesten Pfad vom Startscheitelpunkt zu einem beliebigen Endscheitelpunkt aus dem Wörterbuch zu erhalten, in dem die Kante unmittelbar vor dem berechneten kürzesten Pfad jedes Scheitelpunkts gespeichert ist.

Wie oben in der Berechnungsmethode erwähnt, wird der Knoten unmittelbar vor der kürzesten Entfernung in der Reihenfolge vom letzten Scheitelpunkt (diesmal J) verfolgt und die Kante zur Liste hinzugefügt. Stoppen Sie die Schleife, wenn Sie die Spitze des Starts erreichen. Bevor Sie es zurückgeben, invertieren Sie es mit der revese-Methode, sodass die Reihenfolge vom Startscheitelpunkt zum endgültigen Scheitelpunkt reicht.

def to_route_path_from_path_dict(
        start_vertex_idx: int,
        last_vertex_idx: int,
        path_dict: Dict[int, Edge]) -> RoutePath:
    """
Verwenden Sie ein Wörterbuch, in dem die Kante kurz vor der kürzesten Entfernung gespeichert ist, um diesen Pfad zu erreichen.
Der kürzeste Abstand zum angegebenen Scheitelpunkt

    Parameters
    ----------
    start_vertex_idx : int
Der Scheitelpunkt, der der Ausgangspunkt der Route ist, die Sie suchen möchten
    last_vertex_idx : int
Der Index der Spitze, die der letzte Punkt der Route ist, die Sie finden möchten.
    path_dict : dict
Der Schlüssel ist der Index des Zielscheitelpunkts, und der Wert ist der kürzeste Pfad zu diesem Scheitelpunkt.
Ein Wörterbuch, in dem die vorherige Kante gespeichert ist.
    """
    route_path: RoutePath = []
    current_edge: Edge = path_dict[last_vertex_idx]
    route_path.append(current_edge)
    while current_edge.from_idx != start_vertex_idx:
        current_edge = path_dict[current_edge.from_idx]
        route_path.append(current_edge)
    route_path.reverse()
    return route_path

Verwenden Sie schließlich das vorbereitete Diagramm, instanziieren Sie Knoten, fügen Sie Knoten usw. hinzu und geben Sie die Berechnung und das Berechnungsergebnis aus, um den Vorgang abzuschließen.

if __name__ == '__main__':
    graph = Graph(
        vertices=[
            Vertex.A,
            Vertex.B,
            Vertex.C,
            Vertex.D,
            Vertex.E,
            Vertex.F,
            Vertex.G,
            Vertex.H,
            Vertex.I,
            Vertex.J,
            Vertex.K,
        ])

    graph.add_edge_by_vertices(
        from_vertex=Vertex.A,
        to_vertex=Vertex.B,
        weight=80)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.A,
        to_vertex=Vertex.E,
        weight=200)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.C,
        weight=92)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.D,
        weight=83)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.E,
        weight=210)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.D,
        weight=43)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.E,
        weight=93)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.F,
        weight=66)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.D,
        to_vertex=Vertex.G,
        weight=95)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.D,
        to_vertex=Vertex.H,
        weight=123)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.E,
        to_vertex=Vertex.F,
        weight=81)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.F,
        to_vertex=Vertex.G,
        weight=46)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.F,
        to_vertex=Vertex.K,
        weight=100)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.H,
        weight=141)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.I,
        weight=53)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.K,
        weight=112)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.H,
        to_vertex=Vertex.I,
        weight=86)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.I,
        to_vertex=Vertex.J,
        weight=95)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.J,
        to_vertex=Vertex.K,
        weight=92)

    print('-' * 20)
    print('Diagramminformationen:')
    print(graph)
    print('-' * 20)

    distances, path_dict = dijkstra(
        graph=graph,
        root_vertex=Vertex.A)
    print('Informationen zur kürzesten Entfernung vom berechneten Scheitelpunkt A zu jedem Scheitelpunkt:')
    for index, distance in enumerate(distances):
        vertex: VertexStr = graph.vertex_at(index=index)
        print('Scheitel:', vertex, 'Entfernung:', distance)
    print('-' * 20)

    start_vertex_idx = graph.index_of(vertex=Vertex.A)
    last_vertex_idx = graph.index_of(vertex=Vertex.J)
    route_path: RoutePath = to_route_path_from_path_dict(
        start_vertex_idx=start_vertex_idx,
        last_vertex_idx=last_vertex_idx,
        path_dict=path_dict)
    print('Kürzester Weg von den Eckpunkten A zu den Eckpunkten J.:')
    for edge in route_path:
        print(edge)

Die Diagramminformationen werden wie folgt ausgegeben.

Diagramminformationen:
Zielscheitelpunkte: A ->Benachbarte Scheitelpunktdaten: [('B', 80), ('E', 200)]
Zielscheitelpunkte: B ->Benachbarte Scheitelpunktdaten: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
Zielscheitelpunkte: C ->Benachbarte Scheitelpunktdaten: [('B', 92), ('D', 43), ('E', 93), ('F', 66)]
Zielscheitelpunkte: D ->Benachbarte Scheitelpunktdaten: [('B', 83), ('C', 43), ('G', 95), ('H', 123)]
Zielscheitelpunkte: E ->Benachbarte Scheitelpunktdaten: [('A', 200), ('B', 210), ('C', 93), ('F', 81)]
Zielscheitelpunkte: F ->Benachbarte Scheitelpunktdaten: [('C', 66), ('E', 81), ('G', 46), ('K', 100)]
Zielscheitelpunkte: G ->Benachbarte Scheitelpunktdaten: [('D', 95), ('F', 46), ('H', 141), ('I', 53), ('K', 112)]
Zielscheitelpunkte: H ->Benachbarte Scheitelpunktdaten: [('D', 123), ('G', 141), ('I', 86)]
Zielscheitelpunkte: I ->Benachbarte Scheitelpunktdaten: [('G', 53), ('H', 86), ('J', 95)]
Zielscheitelpunkte: J ->Benachbarte Scheitelpunktdaten: [('I', 95), ('K', 92)]
Zielscheitelpunkte: K ->Benachbarte Scheitelpunktdaten: [('F', 100), ('G', 112), ('J', 92)]

Der kürzeste Abstand zu jedem Scheitelpunkt wird wie folgt ausgegeben.

Informationen zur kürzesten Entfernung vom berechneten Scheitelpunkt A zu jedem Scheitelpunkt:
Scheitel:Ein Abstand: 0
Scheitel:B Abstand: 80
Scheitel:C Abstand: 172
Scheitel:D Abstand: 163
Scheitel:E Entfernung: 200
Scheitel:F Entfernung: 238
Scheitel:G Abstand: 258
Scheitel:H Entfernung: 286
Scheitel:Ich distanziere mich: 311
Scheitel:J Entfernung: 406
Scheitel:K Entfernung: 338

Und der kürzeste Weg wurde berechnet als A → B → D → G → I → J.

Kürzester Weg von den Eckpunkten A zu den Eckpunkten J.:
from: A(weight: 80) -> to: B
from: B(weight: 83) -> to: D
from: D(weight: 95) -> to: G
from: G(weight: 53) -> to: I
from: I(weight: 95) -> to: J

Wenn man sich das Bild des Diagramms ansieht, scheint es sicherlich zu passen.

ダイクストラ法_1.png

Beiseite

Bitte verzeihen Sie Masakari, der über fundierte Kenntnisse auf dem Gebiet der Informatik verfügt.

Ganzer Code

from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop

VertexStr = str


class Vertex:
    """Eine Klasse, die Konstanten von Zeichenfolgen verarbeitet, die jeden Scheitelpunkt darstellen.
    """

    A: VertexStr = 'A'
    B: VertexStr = 'B'
    C: VertexStr = 'C'
    D: VertexStr = 'D'
    E: VertexStr = 'E'
    F: VertexStr = 'F'
    G: VertexStr = 'G'
    H: VertexStr = 'H'
    I: VertexStr = 'I'
    J: VertexStr = 'J'
    K: VertexStr = 'K'


class Edge:

    def __init__(
            self, from_idx: int, to_idx: int,
            from_vertex: VertexStr, to_vertex: VertexStr,
            weight: float) -> None:
        """
Eine Klasse, die eine einzelne Kante behandelt.

        Parameters
        ----------
        from_idx : int
Index des Verbindungsquellenscheitelpunkts.
        to_idx : int
Index des verbundenen Scheitelpunkts.
        weight : float
Kantengewicht.
        """
        self.from_idx: int = from_idx
        self.to_idx: int = to_idx
        self.from_vertex: VertexStr = from_vertex
        self.to_vertex: VertexStr = to_vertex
        self.weight: float = weight

    def reversed(self) -> Edge:
        """
Holen Sie sich die Kante mit der Verbindungsquelle und dem Ziel der Scheitelpunkte invertiert.

        Returns
        -------
        reversed_edge : Edge
Eine Kante, bei der die Verbindungsquelle und das Ziel der Scheitelpunkte invertiert sind.
        """
        reversed_edge = Edge(
            from_idx=self.to_idx,
            to_idx=self.from_idx,
            from_vertex=self.from_vertex,
            to_vertex=self.to_vertex,
            weight=self.weight)
        return reversed_edge

    def __str__(self) -> str:
        """
Konvertieren Sie Kanteninformationen in eine Zeichenfolge.

        Returns
        -------
        edge_info_str : str
Eine Zeichenfolge konvertierter Kanteninformationen.
        """
        edge_info_str: str = (
            f'from: {self.from_vertex}'
            f'(weight: {self.weight})'
            f' -> to: {self.to_vertex}'
        )
        return edge_info_str


class Graph:

    def __init__(self, vertices: List[VertexStr]) -> None:
        """
Eine Klasse zum Arbeiten mit Grafiken.

        Parameters
        ----------
        vertices : list of str
Eine Liste von Eckpunktfolgen.
        """
        self._vertices: List[VertexStr] = vertices
        self._edges: List[List[Edge]] = []
        for _ in vertices:
            self._edges.append([])

    def vertex_at(self, index: int) -> VertexStr:
        """
Ruft die Zeichenfolge der Scheitelpunkte des angegebenen Index ab.

        Parameters
        ----------
        index : int
Zielindex.

        Returns
        -------
        vertex_str : str
Eine Folge von Eckpunkten an der Zielindexposition.
        """
        return self._vertices[index]

    def index_of(self, vertex: VertexStr) -> int:
        """
Holen Sie sich den Intex des Zielscheitelpunkts.

        Parameters
        ----------
        vertex : str
Eine Zeichenfolge zur Identifizierung des Zielscheitelpunkts.

        Returns
        -------
        index : int
Index des Zielscheitelpunkts.
        """
        return self._vertices.index(vertex)

    @property
    def vertex_count(self):
        """
Attributwert der festgelegten Anzahl von Eckpunkten.

        Returns
        -------
        vertex_count : int
Die Anzahl der Scheitelpunkte, die festgelegt wurden.
        """
        return len(self._vertices)

    def edges_at(self, vertex_index: int) -> List[Edge]:
        """
Von der am Scheitelpunkt der angegebenen Indexposition eingestellten Kante
Holen Sie sich die Liste.

        Parameters
        ----------
        vertex_index : int
Index der Zielscheitelpunktposition.

        Returns
        -------
        edges : list of Edge
Eine Liste der Kanten, die für den Zielscheitelpunkt festgelegt wurden.
        """
        return self._edges[vertex_index]

    def get_neighbor_vertices_and_weights_by_index(
            self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
        """
Verbunden mit den Eckpunkten des angegebenen Index mit einer Kante
Rufen Sie eine Liste mit Tupeln mit Gewichtswerten für einen Scheitelpunkt und seine Kanten ab.

        Parameters
        ----------
        vertex_index : int
Index des Zielscheitelpunkts.

        Returns
        -------
        neighbor_vertices_and_weights : list of tuple
Eine Liste mit Tapples berechneter Eckpunkte und deren Kantengewichten.
        """
        neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
        for edge in self.edges_at(vertex_index=vertex_index):
            tuple_val = (
                self.vertex_at(index=edge.to_idx),
                edge.weight,
            )
            neighbor_vertices_and_weights.append(tuple_val)
        return neighbor_vertices_and_weights

    def add_edge(self, edge: Edge) -> None:
        """
Fügen Sie dem Diagramm Kanten hinzu.

        Notes
        -----
Zu den verbundenen Scheitelpunkten werden auch umgekehrte Kanten hinzugefügt (Kanten sind
Durch Ausführen der Methode werden insgesamt 2 Elemente hinzugefügt.

        Parameters
        ----------
        edge : Edge
Die hinzuzufügende Kante.
        """
        self._edges[edge.from_idx].append(edge)
        self._edges[edge.to_idx].append(edge.reversed())

    def add_edge_by_vertices(
            self, from_vertex: VertexStr,
            to_vertex: VertexStr,
            weight: float) -> None:
        """
Fügt eine Kante zwischen den beiden angegebenen Scheitelpunkten hinzu.

        Parameters
        ----------
        from_vertex : str
Geben Sie den Scheitelpunkt der Verbindungsquelle an.
        to_vertex : str
Geben Sie den Scheitelpunkt an, zu dem eine Verbindung hergestellt werden soll.
        weight : float
Kantengewichtswert.
        """
        from_idx = self._vertices.index(from_vertex)
        to_idx = self._vertices.index(to_vertex)
        edge = Edge(
            from_idx=from_idx,
            to_idx=to_idx,
            from_vertex=from_vertex,
            to_vertex=to_vertex,
            weight=weight)
        self.add_edge(edge=edge)

    def __str__(self) -> str:
        """
Gibt die Zeichenfolge der Diagramminformationen zurück.

        Returns
        -------
        graph_info : str
Eine Zeichenfolge mit Diagramminformationen.
        """
        graph_info: str = ''
        for index in range(self.vertex_count):
            neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
                vertex_index=index)
            graph_info += (
                f'Zielscheitelpunkte: {self.vertex_at(index=index)}'
                f' ->Benachbarte Scheitelpunktdaten: {neighbors_data}\n'
            )
        return graph_info


class DijkstraDistanceVertex:

    def __init__(self, vertex_idx: int, distance: float) -> None:
        """
Abstand (Gewicht) vom Beginn eines bestimmten Scheitelpunkts für die Dyxtra-Methode
Eine Klasse zur Vergleichskontrolle mit anderen Eckpunkten.

        Parameters
        ----------
        vertex : str
Index zur Identifizierung des Zielscheitelpunkts.
        distance : float
Abstand von der Spitze des Starts.
        """
        self.vertex_idx = vertex_idx
        self.distance = distance

    def __lt__(self, other: DijkstraDistanceVertex) -> bool:
        """
Erfasst den Wahrheitswert des Vergleichsergebnisses der Entfernung (Gewicht) anderer Eckpunkte.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Der zu vergleichende Scheitelpunkt.

        Returns
        -------
        result : bool
Wenn True und die geringere Bedingung erfüllt ist.
        """
        return self.distance < other.distance

    def __eq__(self, other: DijkstraDistanceVertex) -> bool:
        """
Boolescher Wert, ob der Abstand (Gewicht) mit anderen Scheitelpunkten übereinstimmt
erhalten.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Der zu vergleichende Scheitelpunkt.

        Returns
        -------
        result : bool
Wenn True und die Übereinstimmungsbedingung erfüllt ist.
        """
        return self.distance == other.distance


class PriorityQueue:

    def __init__(self) -> None:
        """
Eine Klasse, die Prioritätswarteschlangen verarbeitet.
        """
        self._container: List[DijkstraDistanceVertex] = []

    @property
    def empty(self) -> bool:
        """
Boolesches Attribut, ob die Warteschlange leer ist.

        Returns
        -------
        result : bool
True wird gesetzt, wenn die Warteschlange leer ist.
        """
        return not self._container

    def push(self, item: DijkstraDistanceVertex) -> None:
        """
Behandeln Sie den Abstand vom Beginn eines bestimmten Scheitelpunkts der Dyxtra-Methode zur Warteschlange
Fügen Sie eine Instanz hinzu.

        Parameters
        ----------
        item : DijkstraDistanceVertex
Die hinzuzufügende Instanz.
        """
        heappush(self._container, item)

    def pop(self) -> DijkstraDistanceVertex:
        """
Extrahieren Sie eine Instanz entsprechend der Priorität aus der Warteschlange.

        Returns
        -------
        item : DijkstraDistanceVertex
Die abgerufene Instanz.
        """
        return heappop(self._container)


def dijkstra(
        graph: Graph,
        root_vertex: VertexStr
        ) -> tuple[List[Optional[float]], Dict[int, Edge]]:
    """
Führen Sie die Dikstra-Methode, den Abstand für jeden Scheitelpunkt und den kürzesten Weg zu jedem Scheitelpunkt aus
Berechnen Sie den Pfad.

    Parameters
    ----------
    graph : Graph
Zieldiagramm.
    root_vertex : str
Eine Zeichenfolge zum Identifizieren des Scheitelpunkts an der Position, an der die Suche gestartet wird.

    Returns
    -------
    distances : list of float
Der Abstand von der Spitze der Suchstartposition jedes Scheitelpunkts.
    path_dict : dict
Der Schlüssel ist der Index des Zielscheitelpunkts, und der Wert ist der Index des Zielscheitelpunkts.
Speichert die unmittelbar vorhergehende Kante der kürzesten Route.
    """
    first_idx: int = graph.index_of(vertex=root_vertex)
    distances: List[Optional[float]] = [
        None for _ in range(graph.vertex_count)]
    distances[first_idx] = 0

    path_dict: Dict[int, Edge] = {}
    priority_queue: PriorityQueue = PriorityQueue()
    priority_queue.push(
        item=DijkstraDistanceVertex(
            vertex_idx=first_idx,
            distance=0))

    while not priority_queue.empty:
        from_idx:int = priority_queue.pop().vertex_idx
        from_vertex_distance: float = distances[from_idx]
        for edge in graph.edges_at(vertex_index=from_idx):

            #Bereits vor der Zieliteration auf den Zielscheitelpunkt gesetzt
            #Holen Sie sich die Entfernung (Wert, der durch eine andere Route festgelegt wurde usw.).
            to_distance: Optional[float] = distances[edge.to_idx]

            #Berechnen Sie die Entfernung auf dieser Route.
            current_route_distance: float = edge.weight + from_vertex_distance

            #Wenn die Entfernung auf einer anderen Route bereits eingestellt wurde und auf dieser Route
            #Wenn die Entfernung nicht kürzer ist, wird der Aktualisierungsvorgang übersprungen.
            if (to_distance is not None
                    and to_distance <= current_route_distance):
                continue

            distances[edge.to_idx] = current_route_distance
            path_dict[edge.to_idx] = edge
            priority_queue.push(
                item=DijkstraDistanceVertex(
                    vertex_idx=edge.to_idx,
                    distance=current_route_distance))

    return distances, path_dict


RoutePath = List[Edge]


def to_route_path_from_path_dict(
        start_vertex_idx: int,
        last_vertex_idx: int,
        path_dict: Dict[int, Edge]) -> RoutePath:
    """
Verwenden Sie ein Wörterbuch, in dem die Kante kurz vor der kürzesten Entfernung gespeichert ist, um diesen Pfad zu erreichen.
Der kürzeste Abstand zum angegebenen Scheitelpunkt

    Parameters
    ----------
    start_vertex_idx : int
Der Scheitelpunkt, der der Ausgangspunkt der Route ist, die Sie suchen möchten
    last_vertex_idx : int
Der Index der Spitze, die der letzte Punkt der Route ist, die Sie finden möchten.
    path_dict : dict
Der Schlüssel ist der Index des Zielscheitelpunkts, und der Wert ist der kürzeste Pfad zu diesem Scheitelpunkt.
Ein Wörterbuch, in dem die vorherige Kante gespeichert ist.
    """
    route_path: RoutePath = []
    current_edge: Edge = path_dict[last_vertex_idx]
    route_path.append(current_edge)
    while current_edge.from_idx != start_vertex_idx:
        current_edge = path_dict[current_edge.from_idx]
        route_path.append(current_edge)
    route_path.reverse()
    return route_path


if __name__ == '__main__':
    graph = Graph(
        vertices=[
            Vertex.A,
            Vertex.B,
            Vertex.C,
            Vertex.D,
            Vertex.E,
            Vertex.F,
            Vertex.G,
            Vertex.H,
            Vertex.I,
            Vertex.J,
            Vertex.K,
        ])

    graph.add_edge_by_vertices(
        from_vertex=Vertex.A,
        to_vertex=Vertex.B,
        weight=80)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.A,
        to_vertex=Vertex.E,
        weight=200)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.C,
        weight=92)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.D,
        weight=83)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.B,
        to_vertex=Vertex.E,
        weight=210)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.D,
        weight=43)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.E,
        weight=93)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.C,
        to_vertex=Vertex.F,
        weight=66)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.D,
        to_vertex=Vertex.G,
        weight=95)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.D,
        to_vertex=Vertex.H,
        weight=123)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.E,
        to_vertex=Vertex.F,
        weight=81)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.F,
        to_vertex=Vertex.G,
        weight=46)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.F,
        to_vertex=Vertex.K,
        weight=100)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.H,
        weight=141)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.I,
        weight=53)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.G,
        to_vertex=Vertex.K,
        weight=112)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.H,
        to_vertex=Vertex.I,
        weight=86)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.I,
        to_vertex=Vertex.J,
        weight=95)
    graph.add_edge_by_vertices(
        from_vertex=Vertex.J,
        to_vertex=Vertex.K,
        weight=92)

    print('-' * 20)
    print('Diagramminformationen:')
    print(graph)
    print('-' * 20)

    distances, path_dict = dijkstra(
        graph=graph,
        root_vertex=Vertex.A)
    print('Informationen zur kürzesten Entfernung vom berechneten Scheitelpunkt A zu jedem Scheitelpunkt:')
    for index, distance in enumerate(distances):
        vertex: VertexStr = graph.vertex_at(index=index)
        print('Scheitel:', vertex, 'Entfernung:', distance)
    print('-' * 20)

    start_vertex_idx = graph.index_of(vertex=Vertex.A)
    last_vertex_idx = graph.index_of(vertex=Vertex.J)
    route_path: RoutePath = to_route_path_from_path_dict(
        start_vertex_idx=start_vertex_idx,
        last_vertex_idx=last_vertex_idx,
        path_dict=path_dict)
    print('Kürzester Weg von den Eckpunkten A zu den Eckpunkten J.:')
    for edge in route_path:
        print(edge)

Referenzseite / Referenzzusammenfassung

Classic Computer Science Problems in Python
Dixtra-Methode (Problem mit der kürzesten Route)
[Peak (Graphentheorie) -Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%82%E7%82%B9_(%E3%82%B0%E3%83%A9%E3) % 83% 95% E7% 90% 86% E8% AB% 96))
Graphentheorie-Wikipedia
Graphentheorie

[GO] Berechnen Sie die kürzeste Route eines Diagramms mit der Dyxtra-Methode und Python