Wie implementiert man den Dijkstra-Algorithmus mit Python?

Wie implementiert man den Dijkstra-Algorithmus mit Python?

Einführung:
Dijkstras Algorithmus ist ein häufig verwendeter Single-Source-Algorithmus für den kürzesten Pfad, mit dem das Problem des kürzesten Pfads zwischen zwei Scheitelpunkten in einem gewichteten Diagramm gelöst werden kann. In diesem Artikel wird detailliert beschrieben, wie Sie Python zum Implementieren des Dijkstra-Algorithmus verwenden, einschließlich Algorithmusprinzipien und spezifischer Codebeispiele.

1. Algorithmusprinzip
   Die Kernidee des Dijkstra-Algorithmus besteht darin, schrittweise den kürzesten Weg vom Quellpunkt zu anderen Scheitelpunkten zu bestimmen, indem kontinuierlich der Scheitelpunkt ausgewählt wird, der dem Quellpunkt am nächsten liegt. Der Algorithmus ist hauptsächlich in die folgenden Schritte unterteilt:
   (1) Initialisierung: Stellen Sie den Abstand vom Quellpunkt zu anderen Eckpunkten auf unendlich und den Abstand vom Quellpunkt zu sich selbst auf 0 ein. Erstellen Sie gleichzeitig ein Wörterbuch, das den kürzesten Weg aufzeichnet, und eine Sammlung, die die besuchten Scheitelpunkte aufzeichnet.
   (2) Wählen Sie den nicht besuchten Scheitelpunkt aus, der dem Quellpunkt derzeit am nächsten liegt, markieren Sie ihn als besucht und aktualisieren Sie den Abstand vom Quellpunkt zu seinen angrenzenden Scheitelpunkten.
   (3) Wiederholen Sie die obigen Schritte, bis alle Stützpunkte besucht wurden oder derzeit keine auswählbaren Stützpunkte vorhanden sind.
2. Code-Implementierung
   Das Folgende ist ein Codebeispiel mit Python zur Implementierung des Dijkstra-Algorithmus:

import sys

def dijkstra(graph, start):
    # 初始化
    distances = {vertex: sys.maxsize for vertex in graph}  # 记录源点到各顶点的距离
    distances[start] = 0
    visited = set()
    previous_vertices = {vertex: None for vertex in graph}  # 记录最短路径的前驱结点

    while graph:
        # 选择当前距离源点最近的未访问顶点
        current_vertex = min(
            {vertex: distances[vertex] for vertex in graph if vertex not in visited},
            key=distances.get
        )

        # 标记为已访问
        visited.add(current_vertex)

        # 更新当前顶点的相邻顶点的距离
        for neighbor in graph[current_vertex]:
            distance = distances[current_vertex] + graph[current_vertex][neighbor]
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_vertices[neighbor] = current_vertex

        # 当前顶点从图中移除
        graph.pop(current_vertex)

    return distances, previous_vertices


# 示例使用
if __name__ == '__main__':
    # 定义图结构（字典表示）
    graph = {
        'A': {'B': 5, 'C': 1},
        'B': {'A': 5, 'C': 2, 'D': 1},
        'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
        'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
        'E': {'C': 8, 'D': 3},
        'F': {'D': 6}
    }

    start_vertex = 'A'
    distances, previous_vertices = dijkstra(graph, start_vertex)

    # 打印结果
    for vertex in distances:
        path = []
        current_vertex = vertex
        while current_vertex is not None:
            path.insert(0, current_vertex)
            current_vertex = previous_vertices[current_vertex]
        print(f'最短路径: {path}, 最短距离: {distances[vertex]}')

Das obige Codebeispiel zeigt, wie der Dijkstra-Algorithmus verwendet wird, um den kürzesten Pfad und die kürzeste Entfernung vom Quellpunkt zu jedem Scheitelpunkt in einem gegebenen Punkt zu finden Diagrammstruktur.

Fazit:
Dieser Artikel stellt die Prinzipien des Dijkstra-Algorithmus im Detail vor und gibt Codebeispiele für die Implementierung des Dijkstra-Algorithmus mit Python. Leser können den Beispielcode ändern und erweitern, um ihn auf komplexere Szenarien anzuwenden. Durch die Beherrschung dieses Algorithmus können Leser das Problem der kürzesten Pfade in gewichteten Diagrammen besser lösen.

Das obige ist der detaillierte Inhalt vonWie implementiert man den Dijkstra-Algorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!