Dijkstra's algorithm

Dijkstra's algorithm 伪代码.py

#伪代码：

Dijkstra(G, s):
    while not every vertex has been visited:
        visit(unmarked vertex v for which distTo(v) is minimized)

visit(v):
    mark(v)
    for each edge e of s:
        relax(e)          # 这一步是对访问的节点的每个 edge 进行计算

relax(e):
    v = e.source
    w = e.target        
    currentBestKnownWeight = distTo(w)  # 已经记录的最小距离
    possiblyBetterWeight = distTo(v) + e.weight  # 前一个距离加上这一个的权重
    if possiblyBetterWeight < currentBestKnownWeight:
        Use e instead of whatever we were using before  # 更新 distTo 和 之前的节点

Dijkstra's algorithm 原理.md

算法复杂度 {\displaystyle \Theta (|E|+|V|\log |V|)}

记录从某个源到每个其他顶点的最短路径

• 设计两个list, 一个是访问过的节点(mark)，一个是未访问过的节点(unmarked vertex)
• 再设计两个list,一个存储最小路径(distTo)，一个储存访问的前一个节点
• A -> A 的距离是 0， A 到其他节点的距离是 无穷大
• 检查 A 的未访问的邻居，计算每个邻居到起始点的距离，如果比记录的最短距离小，则更新最小路径和访问的前一个节点
• 访问过的节点增加 A，未访问的节点删除 A， A访问完毕
• 选择记录距离最小的未访问过的节点，重复以上操作，直到 unvisited 节点没有了