Dijkstra 算法详解

Dijkstra算法简介

Dijkstra算法是由荷兰计算机科学家Edsger Dijkstra于1959年提出的一种求解最短路径问题的算法。该算法采用贪心策略，通过不断地选择距离当前点最近的未访问过的顶点，逐步扩展到其余顶点，直至扩展到目标顶点。

算法原理

Dijkstra算法的核心思想是：

1. 初始化：将所有顶点分为两个集合，一个已访问的集合S，一个未访问的集合U。初始时，S中仅包含起点，U包含除起点外的所有顶点。
2. 迭代：在U中，找到距离起点最近的顶点v，并将其加入S。然后，更新与v相邻的所有顶点的距离。
3. 终止：当U中只剩下目标顶点时，迭代结束。此时，起点到目标顶点的最短路径已找到。

代码实现

以下是一个使用Python实现的Dijkstra算法的示例：

import sys

def dijkstra(graph, start):
    shortest_paths = {start: (None, 0)}
    current_node = start
    visited = set()

    while current_node is not None:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)

        next_destinations = {
            node: shortest_paths[node][1]
            for node in shortest_paths
            if node not in visited
            and shortest_paths[node][1] != float('inf')
        }
        if not next_destinations:
            break
        current_node = min(next_destinations, key=next_destinations.get)

    return shortest_paths

def main(argv):
    graph = {
        'A': {'B': 3, 'C': 4},
        'B': {'A': 3, 'D': 2},
        'C': {'A': 4, 'D': 6, 'E': 2},
        'D': {'B': 2, 'C': 6, 'E': 1},
        'E': {'C': 2, 'D': 1}
    }

    start = 'A'
    shortest_paths = dijkstra(graph, start)
    print("Shortest paths from {}:".format(start))
    for node in shortest_paths:
        print("To {} => {}".format(node, shortest_paths[node]))

if __name__ == "__main__":
    main(sys.argv)