Dijkstra算法用python实现

以下是Dijkstra算法的Python实现，假设图用邻接矩阵表示，起点是节点0：

import sys

def dijkstra(graph, start):
    # 初始化距离值为正无穷
    dist = [sys.maxsize] * len(graph)
    # 起点的距离值为0
    dist[start] = 0
    # 标记是否访问过
    visited = [False] * len(graph)

    for i in range(len(graph)):
        # 选择距离起点最近的节点
        u = find_min_dist(dist, visited)
        visited[u] = True
        # 更新与该节点相邻的节点的距离值
        for v in range(len(graph)):
            if not visited[v] and graph[u][v] > 0 and dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]

    return dist

def find_min_dist(dist, visited):
    # 找到距离起点最近的节点
    min_dist = sys.maxsize
    min_index = -1
    for v in range(len(dist)):
        if not visited[v] and dist[v] < min_dist:
            min_dist = dist[v]
            min_index = v
    return min_index

# 示例
graph = [
    [0, 2, 4, 0, 0, 0],
    [0, 0, 1, 4, 2, 0],
    [0, 0, 0, 0, 3, 0],
    [0, 0, 0, 0, 0, 2],
    [0, 0, 0, 3, 0, 2],
    [0, 0, 0, 0, 0, 0]
]
start = 0
dist = dijkstra(graph, start)
print(dist)

在上面的代码中，我们使用了sys.maxsize来代表正无穷。函数find_min_dist用于找到距离起点最近的节点，函数dijkstra用于计算最短路径。我们将图用邻接矩阵表示，节点之间的距离用整数表示。在示例中，我们使用了一个图来演示算法的运行。