Wie schreibe ich einen Algorithmus für den kürzesten Pfad in Python?

Wie schreibe ich den kürzesten Pfadalgorithmus in Python?

Der Algorithmus für den kürzesten Pfad ist ein Algorithmus, der verwendet wird, um den kürzesten Pfad von einem Startknoten zu einem Zielknoten in einem Diagramm mit gewichteten Kanten zu finden. Unter ihnen sind die beiden bekanntesten und klassischsten Algorithmen der Dijkstra-Algorithmus und der A*-Algorithmus. In diesem Artikel wird erläutert, wie Sie beide Algorithmen mit Python schreiben, und es werden Codebeispiele bereitgestellt.

1. Dijkstra-Algorithmus

Dijkstra-Algorithmus ist ein gieriger Algorithmus zum Finden des kürzesten Pfades in einem Diagramm mit nicht negativen Kantengewichten. Es beginnt mit einem Startknoten und wird schrittweise auf andere Knoten erweitert, bis der Zielknoten gefunden oder alle möglichen Knoten erweitert sind. Die spezifischen Schritte sind wie folgt:

1) Erstellen Sie eine Menge S, um die Knoten des ermittelten kürzesten Pfades zu speichern.
2) Initialisieren Sie den Startknoten als aktuellen Knoten, setzen Sie seine kürzeste Pfadlänge auf 0 und setzen Sie die kürzeste Pfadlänge anderer Knoten auf unendlich.
3) Durchlaufen Sie die Knoten neben dem aktuellen Knoten und aktualisieren Sie ihre kürzeste Pfadlänge auf die Pfadlänge des aktuellen Knotens plus das Gewicht der Kante.
4) Wählen Sie den nächstgelegenen Knoten aus den Knoten mit unbestimmtem kürzestem Pfad als neuen aktuellen Knoten aus und fügen Sie ihn der Menge S hinzu.
5) Wiederholen Sie die Schritte 3 und 4, bis festgestellt wird, dass der Zielknoten der kürzeste Weg ist, und der Algorithmus endet.

Das Folgende ist ein Codebeispiel für die Implementierung des Dijkstra-Algorithmus in 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. A*-Algorithmus

A*-Algorithmus ist ein Bewertungssuchalgorithmus, der verwendet wird, um den kürzesten Pfad eines gewichteten Diagramms mit einer heuristischen Funktion zu lösen. Es schätzt die Pfadlänge vom aktuellen Knoten zum Zielknoten mithilfe einer heuristischen Funktion und wählt den Knoten mit der kleinsten Schätzung für die Suche aus. Die spezifischen Schritte sind wie folgt:

1) Erstellen Sie eine Prioritätswarteschlange, um Knoten und ihre Bewertungen zu speichern.
2) Initialisieren Sie den Startknoten als aktuellen Knoten und fügen Sie ihn der Prioritätswarteschlange hinzu.
3) Nehmen Sie den Knoten mit der kleinsten Bewertung aus der Prioritätswarteschlange als aktuellen Knoten.
4) Wenn der aktuelle Knoten der Zielknoten ist, endet der Algorithmus und der kürzeste Pfad wird zurückgegeben.
5) Durchlaufen Sie die Knoten neben dem aktuellen Knoten, berechnen Sie deren Bewertung und fügen Sie sie der Prioritätswarteschlange hinzu.
6) Wiederholen Sie die Schritte 3 bis 5, bis der Zielknoten gefunden wird oder die Prioritätswarteschlange leer ist, dann endet der Algorithmus.

Das Folgende ist ein Codebeispiel zum Implementieren des A*-Algorithmus in 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

Zusammenfassung

Anhand des obigen Codebeispiels können wir sehen, wie Python zum Schreiben des Algorithmus für den kürzesten Pfad verwendet wird, einschließlich des Dijkstra-Algorithmus und des A*-Algorithmus . Diese beiden Algorithmen sind sehr effektiv zur Lösung des Kürzeste-Wege-Problems in gewichteten Diagrammen. In praktischen Anwendungen können geeignete Algorithmen entsprechend den spezifischen Anforderungen ausgewählt werden, um die Effizienz und Genauigkeit des Algorithmus zu verbessern.

Das obige ist der detaillierte Inhalt vonWie schreibe ich einen Algorithmus für den kürzesten Pfad in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!