Dijkstra's and A

BFS

我们继续回到 BFS 广度优先算法

其中的思想就是，将你所有正在查找到节点存储在一个队列之中

总是找到最短路径（最少边）。

在无权图中，找到最优成本路径。

在有权图中，不总是找到最优成本。

一旦找到路径，重建实际顶点或边的顺序更难。

从概念上讲，宽度优先搜索（BFS）并行探索许多可能路径，因此不易在进行中存储路径数组/列表。

解决方案：我们可以通过存储每个顶点的前驱来跟踪路径。

深度优先搜索（DFS）使用的内存少于 BFS，更容易重建找到的路径；但 DFS 并不总是找到最短路径，而 BFS 可以。

DFS, BFS, runtime and weight

1. DFS: O(V+E)
2. BFS: O(V+E)
3. runtime: O(V+E)

Dijkstra's algorithm

该算法一般在加权有向图中使用，其思想是：

1. 选择一个源点，并将其距离设为 0，其他顶点的距离设为无穷大。
2. 选择距离源点最近的顶点，并将其标记为已访问。
3. 对于该顶点的每一个邻居顶点，更新其距离。
4. 重复步骤 2 和 3，直到所有顶点都被访问。

算法的运行时间为 O(ElogV)，其中 E 为图中的边数，V 为顶点数。

伪代码:

Dijkstra(G, s):
    for each vertex v in G:
        v.distance = infinity
        v.predecessor = null
    s.distance = 0
    Q = priority queue of vertices
    Q.enqueue(s)
    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v):
                v.distance = u.distance + weight(u, v)
                v.predecessor = u
                Q.decrease_key(v)

---

A* algorithm

A*算法是 Dijkstra 算法的扩展，其思想是：

1. 选择一个源点，并将其距离设为 0，其他顶点的距离设为无穷大。
2. 选择距离源点最近的顶点，并将其标记为已访问。
3. 对于该顶点的每一个邻居顶点，更新其距离。
4. 对于距离源点最近的顶点，更新其距离。
5. 重复步骤 2-4，直到所有顶点都被访问。

相比与 Dijkstra 算法，A*算法在选择下一个顶点时，考虑了到达该顶点的实际距离。

算法的运行时间为 O(ElogV)，其中 E 为图中的边数，V 为顶点数。

伪代码:

A_star(G, s):
    for each vertex v in G:
        v.distance = infinity
        v.predecessor = null
    s.distance = 0
    Q = priority queue of vertices
    Q.enqueue(s)
    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v):
                v.distance = u.distance + weight(u, v)
                v.predecessor = u
                Q.decrease_key(v)
        for each neighbor v of u:
            if v.distance > u.distance + weight(u, v) + heuristic(v, s):
                v.distance = u.distance + weight(u, v) + heuristic(v, s)
                v.predecessor = u
                Q.decrease_key(v)

其中，heuristic(v, s)表示从顶点 v 到源点 s 的估计距离。

A*算法的运行时间比 Dijkstra 算法的运行时间更长，但其在有权图中更加准确。