Comment écrire l'algorithme du plus court chemin en Python ?

Comment écrire l'algorithme du chemin le plus court en Python ?

L'algorithme du chemin le plus court est un algorithme utilisé pour trouver le chemin le plus court d'un nœud de départ à un nœud cible dans un graphique avec des arêtes pondérées. Parmi eux, les deux algorithmes les plus connus et les plus classiques sont l'algorithme de Dijkstra et l'algorithme A*. Cet article décrira comment écrire ces deux algorithmes à l'aide de Python et fournira des exemples de code.

1. Algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme glouton permettant de trouver le chemin le plus court dans un graphique avec des poids de bord non négatifs. Il commence par un nœud de départ et s'étend progressivement à d'autres nœuds jusqu'à ce que le nœud cible soit trouvé ou que tous les nœuds possibles soient développés. Les étapes spécifiques sont les suivantes :

1) Créer un ensemble S pour sauvegarder les nœuds du chemin le plus court déterminé.
2) Initialisez le nœud de départ en tant que nœud actuel, définissez sa longueur de chemin la plus courte sur 0 et définissez la longueur de chemin la plus courte des autres nœuds sur l'infini.
3) Parcourez les nœuds adjacents au nœud actuel et mettez à jour leur longueur de chemin la plus courte pour qu'elle soit la longueur du chemin du nœud actuel plus le poids du bord.
4) Sélectionnez le nœud le plus proche parmi les nœuds avec le chemin le plus court indéterminé comme nouveau nœud actuel et ajoutez-le à l'ensemble S.
5) Répétez les étapes 3 et 4 jusqu'à ce que le nœud cible soit déterminé comme étant le chemin le plus court et que l'algorithme se termine.

Ce qui suit est un exemple de code pour implémenter l'algorithme de Dijkstra en Python :

def dijkstra(graph, start, end):
    # 节点集合
    nodes = set(graph.keys())
    # 起始节点到各个节点的最短路径长度字典
    distance = {node: float('inf') for node in nodes}
    # 起始节点到各个节点的最短路径字典
    path = {node: [] for node in nodes}
    # 起始节点到自身的最短路径长度为0
    distance[start] = 0

    while nodes:
        # 找到当前节点中最小距离的节点
        min_node = min(nodes, key=lambda node: distance[node])
        nodes.remove(min_node)

        for neighbor, weight in graph[min_node].items():
            # 计算经过当前节点到相邻节点的路径长度
            new_distance = distance[min_node] + weight
            if new_distance < distance[neighbor]:
                # 更新最短路径
                distance[neighbor] = new_distance
                path[neighbor] = path[min_node] + [min_node]

    return distance[end], path[end] + [end]

2. Algorithme A*

L'algorithme A* est un algorithme de recherche de valorisation utilisé pour résoudre le chemin le plus court d'un graphe pondéré avec une fonction heuristique. Il estime la longueur du chemin entre le nœud actuel et le nœud cible via une fonction heuristique et sélectionne le nœud avec la plus petite estimation pour la recherche. Les étapes spécifiques sont les suivantes :

1) Créez une file d'attente prioritaire pour stocker les nœuds et leurs valorisations.
2) Initialisez le nœud de départ en tant que nœud actuel et ajoutez-le à la file d'attente prioritaire.
3) Prenez le nœud avec la plus petite valorisation de la file d'attente prioritaire comme nœud actuel.
4) Si le nœud actuel est le nœud cible, l'algorithme se termine et le chemin le plus court est renvoyé.
5) Parcourez les nœuds adjacents au nœud actuel, calculez leur valorisation et ajoutez-les à la file d'attente prioritaire.
6) Répétez les étapes 3 à 5 jusqu'à ce que le nœud cible soit trouvé ou que la file d'attente prioritaire soit vide, puis l'algorithme se termine.

Ce qui suit est un exemple de code pour implémenter l'algorithme A* en Python :

from queue import PriorityQueue

def heuristic(node, end):
    # 启发式函数，估计从当前节点到目标节点的路径长度
    return abs(node[0] - end[0]) + abs(node[1] - end[1])

def a_star(graph, start, end):
    # 起始节点到各个节点的最短路径字典
    path = {start: []}
    # 起始节点到各个节点的路径估值字典
    f_value = {start: heuristic(start, end)}
    # 创建一个优先队列，用于存储节点及其估值
    queue = PriorityQueue()
    queue.put((f_value[start], start))

    while not queue.empty():
        _, current = queue.get()

        if current == end:
            return path[current] + [end]

        for neighbor in graph[current]:
            next_node = path[current] + [current]
            if neighbor not in path or len(next_node) < len(path[neighbor]):
                # 更新最短路径
                path[neighbor] = next_node
                # 更新路径估值
                f_value[neighbor] = len(next_node) + heuristic(neighbor, end)
                queue.put((f_value[neighbor], neighbor))

    return None

Résumé

Grâce à l'exemple de code ci-dessus, nous pouvons voir comment utiliser Python pour écrire l'algorithme du chemin le plus court, y compris l'algorithme de Dijkstra et l'algorithme A* . Ces deux algorithmes sont très efficaces pour résoudre le problème du plus court chemin sur des graphes pondérés. Dans les applications pratiques, des algorithmes appropriés peuvent être sélectionnés en fonction de besoins spécifiques pour améliorer l'efficacité et la précision de l'algorithme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!