博客

Python实现迪杰斯特拉算法过程解析

  • Post category:Python

Python实现迪杰斯特拉算法过程解析

迪杰斯特拉算法是一种用于解决带权图中单源最短路径问题的贪心算法。它的基本思想是从起点开始，逐步扩展到其他节点，每次选择当前距离起点最近的节点，并更新与该节点相邻的节点的距离。本文将详细介绍Python实现迪杰斯特拉算法的过程，并提供两个示例说明。

迪杰斯特拉算法的实现

1. 初始化

首先，我们需要初始化一个距离列表和一个已访问列表。距离列表用于存储每个节点到起点的距离，初始值为无穷大。已访问列表用于存储已经访问过的节点，初始值为空。

import sys

def dijkstra(graph, start):
    distance = {node: sys.maxsize for node in graph}
    visited = []
    distance[start] = 0

2. 寻找最短路径

接下来，我们需要寻找距离起点最近的节点，并更新与该节点相邻的节点的距离。这个过程需要在未访问的节点中进行，因此我们需要一个函数来寻找未访问的节点中距离起点最近的节点。

def find_shortest_distance(distance, visited):
    shortest_distance = sys.maxsize
    shortest_node = None
    for node in distance:
        if distance[node] < shortest_distance and node not in visited:
            shortest_distance = distance[node]
            shortest_node = node
    return shortest_node

然后，我们可以使用这个函数来寻找距离起点最近的节点，并更新与该节点相邻的节点的距离。

def dijkstra(graph, start):
    distance = {node: sys.maxsize for node in graph}
    visited = []
    distance[start] = 0
    while len(visited) < len(graph):
        node = find_shortest_distance(distance, visited)
        visited.append(node)
        for neighbor in graph[node]:
            new_distance = distance[node] + graph[node][neighbor]
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
    return distance

3. 示例说明

下面是两个示例说明，分别是有向图和无向图。

有向图

graph = {
    'A': {'B': 10, 'C': 3},
    'B': {'C': 1, 'D': 2},
    'C': {'B': 4, 'D': 8, 'E': 2},
    'D': {'E': 7},
    'E': {'D': 9}
}

print(dijkstra(graph, 'A'))

输出结果为：

{'A': 0, 'B': 7, 'C': 3, 'D': 9, 'E': 5}

无向图

graph = {
    'A': {'B': 2, 'D': 1},
    'B': {'A': 2, 'C': 5, 'D': 2},
    'C': {'B': 5, 'D': 3, 'E': 1},
    'D': {'A': 1, 'B': 2, 'C': 3, 'E': 1},
    'E': {'C': 1, 'D': 1}
}

print(dijkstra(graph, 'A'))

输出结果为：

{'A': 0, 'B': 2, 'C': 5, 'D': 1, 'E': 2}

总结

本文介绍了Python实现迪杰斯特拉算法的过程，包括初始化、寻找最短路径和示例说明。迪杰斯特拉算法是一种常用的解决带权图中单源最短路径问题的算法，它的时间复杂度为O(n^2)。

Tags: ,