单源最短路径问题 Dijkstra算法详解

1. Dijkstra算法是解决单源最短路径的重要算法，基于贪心策略。具体策略为：

• 1 初始化起始点到所有节点距离distance
• 2 循环不断选择距离最近且未访问的节点
• 3 计算经过该节点到所有其他节点距离是否更近，更近则更新distance
• 4 对所有节点进行遍历，遍历完退出循环

2. 如下例：

3. 详细代码如下：

def load_graph():
    Inf = float('inf')
    N=6
    graph = [[0, 1, 12, Inf, Inf, Inf],
             [Inf, 0, 9, 3, Inf, Inf],
             [Inf, Inf, 0, Inf, 5, Inf],
             [Inf, Inf, 4, 0, 13, 15],
             [Inf, Inf, Inf, Inf, 0, 4],
             [Inf, Inf, Inf, Inf, Inf, 0]]

    return graph,N

def locate_node(distance,visited):
    # 找到距离最近且没有访问的节点，并返回其坐标,-1表示所有节点均已访问
    min_dist = float('inf')
    min_index = -1
    for i,dist in enumerate(distance):
        if dist<min_dist and not visited[i]:
            min_dist = dist
            min_index = i
    return min_index

if __name__ == '__main__':
    #source, dest
    src, dst = 0, 5
    graph,N = load_graph()

    #保存是否访问该节点
    visited = [False]*N
    visited[src]=True

    distance = [graph[src][j] for j in range(N)]

    #dijsktra算法
    while locate_node(distance,visited)!=-1:
        #找到距离最近的,且未被访问的节点，-1表示所有节点均已访问
        cur_node = locate_node(distance, visited)

        for node in range(N):
            if node==src or node==cur_node:
                continue
            if graph[cur_node][node]+distance[cur_node] < distance[node]:
                distance[node] = graph[cur_node][node] + distance[cur_node]
        visited[cur_node]=True

    print(distance)
    assert distance==[0, 1, 8, 4, 13, 17]

4. 优缺点