Dijkstra算法实现（贪心）

Dijkstra算法是一种贪心算法，用于计算带权图中单源最短路径的问题。下面是Dijkstra算法的实现步骤：

1. 初始化：将起点s到所有点的距离d[s]赋值为0，其它点的距离d[v]赋值为无穷大，将所有点的前驱节点prev[v]赋值为None。

2. 确定已经求出最短路径的点集S，起初S只包含起点s。

3. 从未确定最短路径的点中选取距离起点s最近的点v，并将其加入S中。

4. 对于v的每个邻接点w，如果d[v]+c(v,w)<d[w]，则更新d[w]=d[v]+c(v,w)和prev[w]=v。

5. 重复步骤3和4，直到所有点都被加入S中，或者不存在从起点s到该点的路径。

下面是Dijkstra算法的Python实现代码：

# Dijkstra算法实现
def dijkstra(graph, s):
    # 初始化距离和前驱节点
    d = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    d[s] = 0
    # 确定已经求出最短路径的点集S
    S = set()
    # 重复选择距离起点s最近的点v，并将其加入S中
    while S != set(graph):
        v = min((set(d.keys()) - S), key=d.get)
        for w in graph[v]:
            if d[v] + graph[v][w] < d[w]:
                d[w] = d[v] + graph[v][w]
                prev[w] = v
        S.add(v)
    return d, prev

其中，graph是带权图，可以使用字典表示，例如：

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}}

其中，'A'、'B'、'C'、'D'、'E'、'F'为图中的节点，例如，'A': {'B': 5, 'C': 1}表示从节点'A'到节点'B'的距离为5，从节点'A'到节点'C'的距离为1。s为起点。