TL;DR

―― Découvrez la méthode Dyxtra pour calculer l'itinéraire le plus court du graphe. «Nous aborderons également les termes très basiques utilisés en théorie des graphes. ――En fait, écrivez la méthode Dyxtra en Python pour approfondir votre compréhension.

Explication des graphiques et des termes simples ciblés cette fois

Cette fois, nous traiterons les graphiques suivants. Imaginez quelque chose comme une carte d'itinéraire de gare.

ダイクストラ法_1.png

Les parties telles que A et B sont appelées sommet ou nœud. En termes de carte d'itinéraire, ce sera une station d'arrêt.

La partie de la ligne reliant chaque sommet est appelée arête ou côté / branche. En termes de plan d'itinéraire, il correspond à la ligne reliant les stations.

Les nombres sur les bords sont appelés poids et coûts. Ce sera le coût nécessaire pour passer par ce bord. En termes de carte d'itinéraire, cela correspond à la distance entre les stations. Dans cet article, nous traiterons de la distance entre les sommets.

De plus, il existe deux types de graphiques: les graphiques non orientés et les graphiques orientés. La direction du graphe non orienté n'est pas fixée entre les sommets. Vous pouvez aller dans les deux sens. En parlant de la carte d'itinéraire, c'est comme monter et descendre à une certaine station. En revanche, les graphes orientés ne peuvent avancer que dans une direction entre les sommets. Cet article traite du contenu des graphiques non orientés.

Quelle est la méthode Dyxtra?

Dijkstra's Algorithm L'algorithme de Dijkstra est un algorithme de théorie des graphes pour calculer le chemin le plus court d'un graphe.

L'algorithme calcule comment aller d'un sommet particulier à un autre et obtenir la distance la plus courte.

Le contenu est similaire à l'algorithme A \ * mentionné dans l'article que j'ai écrit il y a quelque temps (Ecrire l'algorithme A \ * (A-star) en Python). (Bien qu'il existe des différences telles que l'heuristique).

Le problème à résoudre avec Python cette fois

Calculez le chemin le plus court du sommet A au sommet J en Python dans le graphique ci-dessous, que j'ai mentionné il y a quelque temps.

Contenu du calcul de la méthode Dyxtra

[1] Déterminez le point de départ.
[2]. Stocke la distance entre le sommet de départ et le sommet adjacent à ce sommet dans une liste ou similaire. -Il contient également une référence à l'arête qui a conduit aux sommets adjacents.
[3] Ensuite, déplacez-vous vers le sommet adjacent et stockez la distance entre le sommet de départ et le sommet adjacent à ce sommet. --A ce moment, si la distance du sommet de départ du sommet adjacent est déjà stockée (si la distance au sommet cible est calculée par une autre route), elle n'est stockée que lorsque la distance devient courte. Mettez à jour la valeur de la distance que vous êtes. --Lorsque la distance est mise à jour, la référence de l'arête à ce sommet contenu dans [2] est également mise à jour. -Répétez [4]. [3] et répétez le calcul jusqu'à ce qu'il n'y ait plus de cibles (le calcul de tous les itinéraires est terminé).

Une fois le calcul terminé, si vous souhaitez obtenir la distance la plus courte entre le sommet de départ et n'importe quel sommet, chaque sommet conserve la référence de l'arête immédiatement avant qu'elle ne soit la plus courte pour atteindre ce sommet, donc le dernier Vous pouvez obtenir l'itinéraire le plus court en vous référant au bord dans l'ordre du haut de l'objectif, en remontant vers le haut du départ et en inversant l'itinéraire.

Il est difficile de comprendre si ce ne sont que des lettres, alors je vais y toucher avec un petit chiffre. Premièrement, les parties [1] et [2].

ダイクストラ法_3.png

La partie en rouge est la distance calculée par l'itération de calcul. Tout d'abord, nous commencerons par le haut de A.

Il est naturel du sommet de A au sommet de A, mais la distance est de 0. Maintenez la distance et le bord de ce sommet aux sommets de B et E adjacents à A requis dans [2].

À ce stade, la distance entre les sommets de la cible B et E n'a pas été calculée par d'autres routes, donc cette valeur est conservée telle quelle. À ce stade, la distance la plus courte au sommet de B est de 80 et la distance la plus courte au sommet de E est de 200.

Il stocke également les informations du bord immédiatement avant la distance la plus courte (cette fois, le bord entre A et B et le bord entre A et E).

Ensuite, comme le calcul de [3], déplacez la cible vers le sommet de B. Puisqu'il y a quatre sommets A, C, D et E adjacents aux sommets de B, des calculs sont effectués pour chacun.

Tout d'abord, la distance de B à A, qui est calculée pour revenir par l'itinéraire. À l'origine, la distance de A à A était fixée à 0, donc l'itinéraire A → B → A a une distance de 80 + 80, soit 160. Cette distance étant supérieure à 0, elle ne met pas à jour les références de distance ou d'arête.

De même, pour l'itinéraire de B à E, la distance est de 290, ce qui est déjà supérieur à la distance de 200 pour l'itinéraire de A à E, donc il ne met pas à jour la distance la plus courte et les références de bord.

Puisque la distance de B à C et de B à D n'a pas encore été calculée à partir d'un autre itinéraire, elle sera nouvellement adoptée et retenue comme distance la plus courte.

Lorsque le calcul des sommets de B est terminé à l'étape [3], ce sera comme suit.

ダイクストラ法_4.png

De cette manière, le sommet cible est décalé dans l'ordre, et la mise à jour est répétée lorsque la distance au sommet adjacent n'a pas encore été calculée ou que la distance la plus courte devient plus courte. Les sommets adjacents mis à jour seront ajoutés à la file d'attente ultérieurement en tant que sommets cibles pour le calcul.

Quoi utiliser dans l'implémentation Python

Python 3.8.5

Implémentation en Python

Tout d'abord, importez les modules requis. Comme les annotations de type sont utilisées, ajoutez des annotations et chaque classe du package de saisie. De plus, comme j'utilise une file d'attente prioritaire pour contrôler les sommets à cibler dans le calcul de la méthode Dyxtra (j'ai l'impression que je peux utiliser une file d'attente normale sans l'utiliser), je charge celle du package heapq. ..

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

Ensuite, nous définirons des constantes pour les sommets. VertexStr est un simple alias de type str. Si vous en abusez, il peut être difficile de le distinguer de la classe, mais il est pratique de faire comprendre facilement que "cet argument est une chaîne de constantes aux sommets", je vais donc l'utiliser cette fois.

VertexStr = str


class Vertex:
    """Une classe qui gère les constantes des chaînes qui représentent chaque sommet.
    """

    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'

Ensuite, nous définirons une classe pour l'arête. Contient les informations de sommet et le poids à cette arête (dans ce cas, la distance) dans l'attribut (pour déterminer à quel sommet est l'arête à connecter).

class Edge:

    def __init__(
            self, from_idx: int, to_idx: int,
            from_vertex: VertexStr, to_vertex: VertexStr,
            weight: float) -> None:
        """
Une classe qui gère un seul bord.

        Parameters
        ----------
        from_idx : int
Index du sommet de la source de connexion.
        to_idx : int
Index du sommet connecté.
        weight : float
Poids du bord.
        """
        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

Dans le processus d'ajout d'arête, ajoutez une méthode d'inversion car il est pratique d'ajouter celle dont la direction est inversée (par exemple, générer l'arête du sommet B → sommet A à partir de l'arête du sommet A → sommet B).

    def reversed(self) -> Edge:
        """
Obtenez l'arête avec la source de connexion et la destination des sommets inversées.

        Returns
        -------
        reversed_edge : Edge
Une arête avec la source de connexion et la destination des sommets inversées.
        """
        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

De plus, ajustez le contenu lorsque l'instance de cette classe est sortie par la fonction d'impression, etc. afin que cela soit pratique lors de la sortie de l'itinéraire plus tard. La sortie sera la suivante.

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

    def __str__(self) -> str:
        """
Convertissez les informations de bord en chaîne.

        Returns
        -------
        edge_info_str : str
Une chaîne d'informations de bord converties.
        """
        edge_info_str: str = (
            f'from: {self.from_vertex}'
            f'(weight: {self.weight})'
            f' -> to: {self.to_vertex}'
        )
        return edge_info_str

Ensuite, nous définirons une classe pour le graphe. Pour les arguments vertices, spécifiez une liste de valeurs des constantes de la classe Vertex ultérieurement, telles que «A», «B», «C» ...

Une liste multidimensionnelle est créée en bouclant autant de fois qu'il y a de sommets dans l'attribut _edges. La deuxième dimension stocke plusieurs arêtes connectées au sommet cible. Les arêtes sont toujours vides à ce stade, mais nous les ajouterons plus tard.

class Graph:

    def __init__(self, vertices: List[VertexStr]) -> None:
        """
Une classe pour travailler avec des graphiques.

        Parameters
        ----------
        vertices : list of str
Une liste de chaînes de sommets.
        """
        self._vertices: List[VertexStr] = vertices
        self._edges: List[List[Edge]] = []
        for _ in vertices:
            self._edges.append([])

Nous ajouterons chaque méthode requise pour certains calculs. La première est la méthode pour obtenir les sommets de la position d'index cible.

    def vertex_at(self, index: int) -> VertexStr:
        """
Obtient la chaîne des sommets de l'index spécifié.

        Parameters
        ----------
        index : int
Index cible.

        Returns
        -------
        vertex_str : str
Une chaîne de sommets à la position d'index cible.
        """
        return self._vertices[index]

Inversement, ajoutez une méthode pour obtenir l'index correspondant à partir de la chaîne de sommets.

    def index_of(self, vertex: VertexStr) -> int:
        """
Obtient l'entier du sommet cible.

        Parameters
        ----------
        vertex : str
Une chaîne de caractères pour identifier le sommet cible.

        Returns
        -------
        index : int
Index du sommet cible.
        """
        return self._vertices.index(vertex)

Ajoutez une méthode en tant que propriété du nombre de sommets.

    @property
    def vertex_count(self):
        """
Valeur d'attribut du nombre défini de sommets.

        Returns
        -------
        vertex_count : int
Le nombre de sommets définis.
        """
        return len(self._vertices)

Ajoutez une méthode pour obtenir une liste d'arêtes connectées aux sommets de la position d'index cible.

    def edges_at(self, vertex_index: int) -> List[Edge]:
        """
De l'arête définie au sommet de la position d'index spécifiée
Obtenez la liste.

        Parameters
        ----------
        vertex_index : int
Index de la position du sommet cible.

        Returns
        -------
        edges : list of Edge
Une liste d'arêtes définies pour le sommet cible.
        """
        return self._edges[vertex_index]

Ajoute un processus pour obtenir une liste de tuples qui stockent les poids des sommets adjacents aux sommets spécifiés et à leurs arêtes. Il est utilisé dans le calcul pour calculer les sommets adjacents lorsque la distance la plus courte est calculée pour un sommet spécifique.

    def get_neighbor_vertices_and_weights_by_index(
            self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
        """
Connecté aux sommets de l'index spécifié avec une arête
Obtenez une liste de tuples de valeurs de poids pour un sommet et ses arêtes.

        Parameters
        ----------
        vertex_index : int
Index du sommet cible.

        Returns
        -------
        neighbor_vertices_and_weights : list of tuple
Une liste contenant les tapples des sommets calculés et leurs poids d'arête.
        """
        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

Ajoutez une méthode pour ajouter des arêtes au graphique. Nous voulons également ajouter des arêtes dans la direction opposée pour réduire la description. Par exemple, si une arête dans la direction A → B est ajoutée, une arête dans la direction B → A doit également être ajoutée. Pour générer un bord inversé, utilisez la méthode inversée ajoutée à la classe Edge.

    def add_edge(self, edge: Edge) -> None:
        """
Ajoutez des arêtes au graphique.

        Notes
        -----
Les arêtes inversées sont également ajoutées aux sommets connectés (les arêtes sont
Un total de 2 éléments sera ajouté en exécutant la méthode).

        Parameters
        ----------
        edge : Edge
Le bord à ajouter.
        """
        self._edges[edge.from_idx].append(edge)
        self._edges[edge.to_idx].append(edge.reversed())

Il ajoute également une méthode qui ajoute ensuite des arêtes en fonction des caractères aux deux sommets spécifiés. Cela vous permet d'écrire quelque chose comme "ajouter un bord entre A et B". Puisque la méthode add_edge est appelée en interne, l'arête dans la direction opposée est également ajoutée (sous forme inversée).

À la fin de la classe de graphe, les informations des sommets ajoutés lors de l'impression, etc. et les sommets adjacents (et arêtes) définis pour ces sommets doivent être affichés. La sortie sera la suivante.

Informations graphiques:
Sommets cibles: A ->Données de sommets adjacents: [('B', 80), ('E', 200)]
Sommets cibles: B ->Données de sommets adjacents: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
...

    def __str__(self) -> str:
        """
Renvoie la chaîne de caractères des informations du graphique.

        Returns
        -------
        graph_info : str
Une chaîne d'informations graphiques.
        """
        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'Sommets cibles: {self.vertex_at(index=index)}'
                f' ->Données de sommets adjacents: {neighbors_data}\n'
            )
        return graph_info

Ensuite, ajoutez une classe qui gère la distance entre le sommet de départ et un sommet spécifique par la méthode Dyxtra et décrit le traitement pour calculer le poids (distance).

class DijkstraDistanceVertex:

    def __init__(self, vertex_idx: int, distance: float) -> None:
        """
Distance (poids) depuis le début d'un sommet particulier pour la méthode Dyxtra
Une classe pour le contrôle de comparaison avec d'autres sommets.

        Parameters
        ----------
        vertex : str
Index pour identifier le sommet cible.
        distance : float
Distance du haut du départ.
        """
        self.vertex_idx = vertex_idx
        self.distance = distance

Ajoutez une méthode de comparaison de poids. La méthode Dyxtra est utilisée pour déterminer si l'itinéraire vers un sommet déjà calculé sera raccourci après le calcul.

    def __lt__(self, other: DijkstraDistanceVertex) -> bool:
        """
Acquiert la valeur de vérité du résultat de la comparaison de la distance (poids) des autres sommets.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Le sommet à comparer.

        Returns
        -------
        result : bool
Si Vrai et que la condition la plus faible est remplie.
        """
        return self.distance < other.distance

    def __eq__(self, other: DijkstraDistanceVertex) -> bool:
        """
Valeur booléenne indiquant si la distance (poids) avec d'autres sommets correspond
avoir.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Le sommet à comparer.

        Returns
        -------
        result : bool
Si True et que la condition de correspondance est remplie.
        """
        return self.distance == other.distance

Vient ensuite la préparation de la classe de file d'attente prioritaire. Chaque fois que la distance la plus courte à chaque sommet est mise à jour, ce sommet est ajouté à la file d'attente. Après tout, il est calculé pour tous, il était donc normal d'utiliser une file d'attente normale même si elle n'était pas prioritaire ...? Je n'en ai pas envie.

class PriorityQueue:

    def __init__(self) -> None:
        """
Une classe qui gère les files d'attente prioritaires.
        """
        self._container: List[DijkstraDistanceVertex] = []

    @property
    def empty(self) -> bool:
        """
Attribut booléen indiquant si la file d'attente est vide.

        Returns
        -------
        result : bool
True est défini si la file d'attente est vide.
        """
        return not self._container

    def push(self, item: DijkstraDistanceVertex) -> None:
        """
Gérez la distance entre le début d'un sommet spécifique de la méthode Dyxtra et la file d'attente
Ajoutez une instance.

        Parameters
        ----------
        item : DijkstraDistanceVertex
L'instance à ajouter.
        """
        heappush(self._container, item)

    def pop(self) -> DijkstraDistanceVertex:
        """
Extrayez une instance de la file d'attente en fonction de la priorité.

        Returns
        -------
        item : DijkstraDistanceVertex
L'instance récupérée.
        """
        return heappop(self._container)

Maintenant que nous avons tous les graphiques prêts, écrivons les calculs de la méthode Dyxtra.

def dijkstra(
        graph: Graph,
        root_vertex: VertexStr
        ) -> tuple[List[Optional[float]], Dict[int, Edge]]:
    """
Exécutez la méthode Dikstra, la distance pour chaque sommet et l'itinéraire le plus court vers chaque sommet
Calculez le chemin.

    Parameters
    ----------
    graph : Graph
Graphique cible.
    root_vertex : str
Une chaîne de caractères pour identifier le sommet à la position où la recherche est lancée.

    Returns
    -------
    distances : list of float
La distance par rapport au sommet de la position de départ de la recherche de chaque sommet.
    path_dict : dict
La clé est l'index du sommet cible et la valeur est l'index du sommet cible.
Stocke le bord immédiatement précédent de l'itinéraire le plus court.
    """
    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):

            #Déjà défini sur le sommet cible avant l'itération cible
            #Obtenez la distance (valeur définie par un autre itinéraire, etc.).
            to_distance: Optional[float] = distances[edge.to_idx]

            #Calculez la distance sur cet itinéraire.
            current_route_distance: float = edge.weight + from_vertex_distance

            #Si la distance sur un autre itinéraire a déjà été définie, et sur cet itinéraire
            #Si la distance n'est pas plus courte, le processus de mise à jour est ignoré.
            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

Pour l'argument root_vertex, nous voulons obtenir la route la plus courte de A à J cette fois, alors spécifiez A plus tard.

    while not priority_queue.empty:

Et ainsi de suite, le processus se poursuit avec l'instruction while jusqu'à ce que le sommet à rechercher disparaisse de la file d'attente.

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

Dans l'instruction while, la valeur passée (valeur déjà calculée par un autre itinéraire) est acquise pour la distance au sommet cible du calcul. Initialement, None est défini, donc s'il s'agit du premier pic, ce sera None.

            current_route_distance: float = edge.weight + from_vertex_distance

Calcule la distance actuelle de l'instruction while. Le poids (distance) du bord immédiatement précédent et la distance par rapport au sommet immédiatement précédent sont additionnés.

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

Si la distance calculée par un autre itinéraire existe déjà et que la distance calculée par cette itération ne devient pas plus courte, la mise à jour n'est pas nécessaire et le processus est ignoré.

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

Si la distance est raccourcie ou s'il s'agit du premier sommet à calculer, mettez à jour la distance à ce sommet, mettez à jour les informations de l'arête immédiatement avant la distance la plus courte à ce sommet et calculez ce sommet dans une itération ultérieure. Ajouter à la file d'attente.

    return distances, path_dict

La valeur de retour est une liste qui stocke des informations sur la distance la plus courte à chaque sommet et un dictionnaire qui stocke l'arête immédiatement avant l'itinéraire qui est la distance la plus courte à chaque sommet.

Ensuite, préparez une fonction pour obtenir le chemin le plus court du sommet de départ à tout sommet final du dictionnaire qui stocke l'arête immédiatement avant le chemin le plus court calculé de chaque sommet.

Comme mentionné ci-dessus dans la méthode de calcul, le nœud immédiatement avant la distance la plus courte est tracé dans l'ordre à partir du dernier sommet (J cette fois), et l'arête est ajoutée à la liste. Arrêtez la boucle lorsque vous atteignez le sommet du départ. De plus, avant de le renvoyer, inversez-le avec la méthode revese afin que l'ordre soit du sommet de départ au sommet final.

def to_route_path_from_path_dict(
        start_vertex_idx: int,
        last_vertex_idx: int,
        path_dict: Dict[int, Edge]) -> RoutePath:
    """
En utilisant un dictionnaire qui stocke le bord juste avant la distance la plus courte pour atteindre ce chemin,
La distance la plus courte au sommet spécifié

    Parameters
    ----------
    start_vertex_idx : int
Le sommet qui est le point de départ de l'itinéraire que vous souhaitez trouver
    last_vertex_idx : int
L'index du sommet qui est le point final de l'itinéraire que vous souhaitez rechercher.
    path_dict : dict
La clé est l'index du sommet cible et la valeur est le chemin le plus court vers ce sommet.
Un dictionnaire qui stocke l'arête précédente.
    """
    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

Enfin, en utilisant celui préparé, instanciez le graphique, ajoutez des nœuds, etc., et sortez le calcul et le résultat du calcul pour terminer.

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('Informations graphiques:')
    print(graph)
    print('-' * 20)

    distances, path_dict = dijkstra(
        graph=graph,
        root_vertex=Vertex.A)
    print('Informations sur la distance la plus courte entre le sommet calculé A et chaque sommet:')
    for index, distance in enumerate(distances):
        vertex: VertexStr = graph.vertex_at(index=index)
        print('sommet:', vertex, 'distance:', 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('Chemin le plus court des sommets A aux sommets J:')
    for edge in route_path:
        print(edge)

Les informations du graphique sont sorties comme suit.

Informations graphiques:
Sommets cibles: A ->Données de sommets adjacents: [('B', 80), ('E', 200)]
Sommets cibles: B ->Données de sommets adjacents: [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
Sommets cibles: C ->Données de sommets adjacents: [('B', 92), ('D', 43), ('E', 93), ('F', 66)]
Sommets cibles: D ->Données de sommets adjacents: [('B', 83), ('C', 43), ('G', 95), ('H', 123)]
Sommets cibles: E ->Données de sommets adjacents: [('A', 200), ('B', 210), ('C', 93), ('F', 81)]
Sommets cibles: F ->Données de sommets adjacents: [('C', 66), ('E', 81), ('G', 46), ('K', 100)]
Sommets cibles: G ->Données de sommets adjacents: [('D', 95), ('F', 46), ('H', 141), ('I', 53), ('K', 112)]
Sommets cibles: H ->Données de sommets adjacents: [('D', 123), ('G', 141), ('I', 86)]
Sommets cibles: I ->Données de sommets adjacents: [('G', 53), ('H', 86), ('J', 95)]
Sommets cibles: J ->Données de sommets adjacents: [('I', 95), ('K', 92)]
Sommets cibles: K ->Données de sommets adjacents: [('F', 100), ('G', 112), ('J', 92)]

La distance la plus courte à chaque sommet est sortie comme suit.

Informations sur la distance la plus courte entre le sommet calculé A et chaque sommet:
sommet:Une distance: 0
sommet:Distance B: 80
sommet:Distance C: 172
sommet:Distance D: 163
sommet:Distance E: 200
sommet:Distance F: 238
sommet:Distance G: 258
sommet:Distance H: 286
sommet:Je m'éloigne: 311
sommet:Distance J: 406
sommet:Distance K: 338

Et l'itinéraire le plus court a été calculé comme suit: A → B → D → G → I → J.

Chemin le plus court des sommets A aux sommets 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

En regardant l'image du graphique, il semble sûrement convenir.

ダイクストラ法_1.png

De côté

Diplômé à l'origine d'une école dans le domaine du design, veuillez pardonner à Masakari qui est fort dans le domaine de l'informatique pour des points intellectuellement divers.

Code entier

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

VertexStr = str


class Vertex:
    """Une classe qui gère les constantes des chaînes qui représentent chaque sommet.
    """

    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:
        """
Une classe qui gère un seul bord.

        Parameters
        ----------
        from_idx : int
Index du sommet de la source de connexion.
        to_idx : int
Index du sommet connecté.
        weight : float
Poids du bord.
        """
        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:
        """
Obtenez l'arête avec la source de connexion et la destination des sommets inversées.

        Returns
        -------
        reversed_edge : Edge
Une arête avec la source de connexion et la destination des sommets inversées.
        """
        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:
        """
Convertissez les informations de bord en chaîne.

        Returns
        -------
        edge_info_str : str
Une chaîne d'informations de bord converties.
        """
        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:
        """
Une classe pour travailler avec des graphiques.

        Parameters
        ----------
        vertices : list of str
Une liste de chaînes de sommets.
        """
        self._vertices: List[VertexStr] = vertices
        self._edges: List[List[Edge]] = []
        for _ in vertices:
            self._edges.append([])

    def vertex_at(self, index: int) -> VertexStr:
        """
Obtient la chaîne des sommets de l'index spécifié.

        Parameters
        ----------
        index : int
Index cible.

        Returns
        -------
        vertex_str : str
Une chaîne de sommets à la position d'index cible.
        """
        return self._vertices[index]

    def index_of(self, vertex: VertexStr) -> int:
        """
Obtient l'entier du sommet cible.

        Parameters
        ----------
        vertex : str
Une chaîne de caractères pour identifier le sommet cible.

        Returns
        -------
        index : int
Index du sommet cible.
        """
        return self._vertices.index(vertex)

    @property
    def vertex_count(self):
        """
Valeur d'attribut du nombre défini de sommets.

        Returns
        -------
        vertex_count : int
Le nombre de sommets définis.
        """
        return len(self._vertices)

    def edges_at(self, vertex_index: int) -> List[Edge]:
        """
De l'arête définie au sommet de la position d'index spécifiée
Obtenez la liste.

        Parameters
        ----------
        vertex_index : int
Index de la position du sommet cible.

        Returns
        -------
        edges : list of Edge
Une liste d'arêtes définies pour le sommet cible.
        """
        return self._edges[vertex_index]

    def get_neighbor_vertices_and_weights_by_index(
            self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
        """
Connecté aux sommets de l'index spécifié avec une arête
Obtenez une liste de tuples de valeurs de poids pour un sommet et ses arêtes.

        Parameters
        ----------
        vertex_index : int
Index du sommet cible.

        Returns
        -------
        neighbor_vertices_and_weights : list of tuple
Une liste contenant les tapples des sommets calculés et leurs poids d'arête.
        """
        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:
        """
Ajoutez des arêtes au graphique.

        Notes
        -----
Les arêtes inversées sont également ajoutées aux sommets connectés (les arêtes sont
Un total de 2 éléments sera ajouté en exécutant la méthode).

        Parameters
        ----------
        edge : Edge
Le bord à ajouter.
        """
        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:
        """
Ajoute une arête entre les deux sommets spécifiés.

        Parameters
        ----------
        from_vertex : str
Spécifiez le sommet de la source de connexion.
        to_vertex : str
Spécifiez le sommet auquel se connecter.
        weight : float
Valeur du poids du bord.
        """
        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:
        """
Renvoie la chaîne de caractères des informations du graphique.

        Returns
        -------
        graph_info : str
Une chaîne d'informations graphiques.
        """
        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'Sommets cibles: {self.vertex_at(index=index)}'
                f' ->Données de sommets adjacents: {neighbors_data}\n'
            )
        return graph_info


class DijkstraDistanceVertex:

    def __init__(self, vertex_idx: int, distance: float) -> None:
        """
Distance (poids) depuis le début d'un sommet particulier pour la méthode Dyxtra
Une classe pour le contrôle de comparaison avec d'autres sommets.

        Parameters
        ----------
        vertex : str
Index pour identifier le sommet cible.
        distance : float
Distance du haut du départ.
        """
        self.vertex_idx = vertex_idx
        self.distance = distance

    def __lt__(self, other: DijkstraDistanceVertex) -> bool:
        """
Acquiert la valeur de vérité du résultat de la comparaison de la distance (poids) des autres sommets.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Le sommet à comparer.

        Returns
        -------
        result : bool
Si Vrai et que la condition la plus faible est remplie.
        """
        return self.distance < other.distance

    def __eq__(self, other: DijkstraDistanceVertex) -> bool:
        """
Valeur booléenne indiquant si la distance (poids) avec d'autres sommets correspond
avoir.

        Parameters
        ----------
        other : DijkstraDistanceVertex
Le sommet à comparer.

        Returns
        -------
        result : bool
Si True et que la condition de correspondance est remplie.
        """
        return self.distance == other.distance


class PriorityQueue:

    def __init__(self) -> None:
        """
Une classe qui gère les files d'attente prioritaires.
        """
        self._container: List[DijkstraDistanceVertex] = []

    @property
    def empty(self) -> bool:
        """
Attribut booléen indiquant si la file d'attente est vide.

        Returns
        -------
        result : bool
True est défini si la file d'attente est vide.
        """
        return not self._container

    def push(self, item: DijkstraDistanceVertex) -> None:
        """
Gérez la distance entre le début d'un sommet spécifique de la méthode Dyxtra et la file d'attente
Ajoutez une instance.

        Parameters
        ----------
        item : DijkstraDistanceVertex
L'instance à ajouter.
        """
        heappush(self._container, item)

    def pop(self) -> DijkstraDistanceVertex:
        """
Extrayez une instance de la file d'attente en fonction de la priorité.

        Returns
        -------
        item : DijkstraDistanceVertex
L'instance récupérée.
        """
        return heappop(self._container)


def dijkstra(
        graph: Graph,
        root_vertex: VertexStr
        ) -> tuple[List[Optional[float]], Dict[int, Edge]]:
    """
Exécutez la méthode Dikstra, la distance pour chaque sommet et l'itinéraire le plus court vers chaque sommet
Calculez le chemin.

    Parameters
    ----------
    graph : Graph
Graphique cible.
    root_vertex : str
Une chaîne de caractères pour identifier le sommet à la position où la recherche est lancée.

    Returns
    -------
    distances : list of float
La distance par rapport au sommet de la position de départ de la recherche de chaque sommet.
    path_dict : dict
La clé est l'index du sommet cible et la valeur est l'index du sommet cible.
Stocke le bord immédiatement précédent de l'itinéraire le plus court.
    """
    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):

            #Déjà défini sur le sommet cible avant l'itération cible
            #Obtenez la distance (valeur définie par un autre itinéraire, etc.).
            to_distance: Optional[float] = distances[edge.to_idx]

            #Calculez la distance sur cet itinéraire.
            current_route_distance: float = edge.weight + from_vertex_distance

            #Si la distance sur un autre itinéraire a déjà été définie, et sur cet itinéraire
            #Si la distance n'est pas plus courte, le processus de mise à jour est ignoré.
            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:
    """
En utilisant un dictionnaire qui stocke le bord juste avant la distance la plus courte pour atteindre ce chemin,
La distance la plus courte au sommet spécifié

    Parameters
    ----------
    start_vertex_idx : int
Le sommet qui est le point de départ de l'itinéraire que vous souhaitez trouver
    last_vertex_idx : int
L'index du sommet qui est le point final de l'itinéraire que vous souhaitez rechercher.
    path_dict : dict
La clé est l'index du sommet cible et la valeur est le chemin le plus court vers ce sommet.
Un dictionnaire qui stocke l'arête précédente.
    """
    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('Informations graphiques:')
    print(graph)
    print('-' * 20)

    distances, path_dict = dijkstra(
        graph=graph,
        root_vertex=Vertex.A)
    print('Informations sur la distance la plus courte entre le sommet calculé A et chaque sommet:')
    for index, distance in enumerate(distances):
        vertex: VertexStr = graph.vertex_at(index=index)
        print('sommet:', vertex, 'distance:', 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('Chemin le plus court des sommets A aux sommets J:')
    for edge in route_path:
        print(edge)

Site de référence / résumé de référence

Classic Computer Science Problems in Python
Méthode Dixtra (problème d'itinéraire le plus court)
[Peak (Théorie des graphes) -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))
Théorie des graphes-Wikipedia
Théorie des graphes

Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python