Comment implémenter l'algorithme de Dijkstra en utilisant Python ?

Comment implémenter l'algorithme de Dijkstra en utilisant Python ?

Introduction : 
L'algorithme de Dijkstra est un algorithme de chemin le plus court à source unique couramment utilisé qui peut être utilisé pour résoudre le problème du chemin le plus court entre deux sommets dans un graphe pondéré. Cet article présentera en détail comment utiliser Python pour implémenter l'algorithme de Dijkstra, y compris les principes de l'algorithme et des exemples de code spécifiques.

1. Principe de l'algorithme
   L'idée principale de l'algorithme de Dijkstra est de déterminer progressivement le chemin le plus court du point source vers d'autres sommets en sélectionnant continuellement le sommet le plus proche du point source. L'algorithme est principalement divisé en les étapes suivantes :
   (1) Initialisation : définissez la distance entre le point source et les autres sommets à l'infini et la distance entre le point source et lui-même sur 0. En même temps, créez un dictionnaire qui enregistre le chemin le plus court et une collection qui enregistre les sommets visités.
   (2) Sélectionnez le sommet non visité actuellement le plus proche du point source, marquez-le comme visité et mettez à jour la distance entre le point source et ses sommets adjacents.
   (3) Répétez les étapes ci-dessus jusqu'à ce que tous les sommets aient été visités ou qu'il n'y ait actuellement aucun sommet sélectionnable.
2. Implémentation du code
   Ce qui suit est un exemple de code utilisant Python pour implémenter l'algorithme de Dijkstra :

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]}')

L'exemple de code ci-dessus montre comment utiliser l'algorithme de Dijkstra pour trouver le chemin le plus court et la distance la plus courte entre le point source et chaque sommet dans un champ donné. structure graphique.

Conclusion :
Cet article présente en détail les principes de l'algorithme de Dijkstra et donne des exemples de code pour implémenter l'algorithme de Dijkstra à l'aide de Python. Les lecteurs peuvent modifier et développer l’exemple de code pour l’appliquer à des scénarios plus complexes. En maîtrisant cet algorithme, les lecteurs peuvent mieux résoudre le problème du chemin le plus court dans les graphiques pondérés.

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!