图算法
算法 

图的表示

我们用$V$表示图的结点数，$E$表示图的边的条数。 对于图$G=(V,E)$，可以用两种标准表示方法表示：将图作为邻接链表的组合；将图作为邻接矩阵来看待。 稀疏图（边的条数$E$远远小于$V^2$的图）通常用邻接链表表示，因为邻接链表非常紧凑。 稠密图（边的条数$E$接近$V^2$的图）倾向于用邻接矩阵表示。 权重图 图中的每条边都带有一个相关的权重，该权重值通常是由一个$\omega: E\rightarrow R$的权重函数给出。

广度优先搜索

广度优先搜索 是最简单的图搜索算法之一，也是许多重要的图算法原型。 给定图$G=(V,E)$ 和一个可以识别的源结点$s$，广度会选搜索对图$G$中的边进行系统性的探索来发现可以从源结点$s$到达的所有结点。该算法能够计算从源结点$s$到每个可到达的结点的距离，同时生成一棵“广度会选搜索树”。该树以$s$ 为根结点，包含所有可以从 $s$ 到达的结点。对于每个从源结点 $s$ 可以到达的结点 $v$，在广度优先搜索树里从结点 $s$ 到结点 $v$ 的简单路径所对应的就是图 $G$ 中从结点 $s$ 到结点 $v$ 的 “最短路径”，即包含最少边数的路径。该算法即可以用于有向图，也可以用于无向图。

为了跟踪算法，广度会选搜索在概念上将每个结点涂上白色、灰色或黒色。所有结点在一开始均涂上白色。在搜索过程中第一次遇到一个结点就称该结点被发现，此时将该结点的颜色涂成灰色，并将该结点放到队列的最后。以某结点作为搜索其相邻结点的结点时，该结点涂成黒色。所有结点为黒色时，搜索结束。

伪代码如下：

BFS(G, s)
    for each vertex u in G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.parent = NIL
    s.color = GRAY
    s.d = 0
    s.parent = NIL
    Q = {}
    ENQUEUE(Q, s)
    while Q.size() > 0
        u = DEQUEUE(Q)
        for each v in G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.parent = u
                ENQUEUE(Q,v)
        u.color = BLACK

算法的时间复杂度是 $O(V+E)$ 广度优先搜索的结果可能依赖于对每个结点的邻接结点的访问顺序：广度优先树可能会不一样，相计算出来的距离是d是一样的。

最短路径

定义从源结点 $s$ 到结点 $v$ 的最短距离$\delta (s,v)$ 为从结点 $s$ 到结点 $v$ 之间所有路径里面最少的边数，若结点 $s$ 到结点 $v$ 之间没有路径，则 $\delta(s,v)=\infty$。 结点 $s$ 到结点 $v$ 的最短路径 是结点 $s$ 到结点 $v$ 的长度为 $\delta(s,v)$ 的路径。

深度优先搜索

深度优先搜索 总是对最近才发现对结点 $v$ 的出发边进行探索，直到该节点的所有出发边都被发现为止。一旦 $v$ 的出发边都被发现，搜索则“回溯”到 $v$ 的前驱结点，来搜索该前驱结点的出发边。该过程一直持续支从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些从未被发现的结点中任选一个作为新的源结点，并重复同样的过程，直到所有的结点都被发现。 深度优先搜索的前驱子图可能由多棵树组成，因为搜索可能从多个源结点重复进行。其前驱子图形成一个由多棵深度优先树构成的深度优先森林： $G_\pi=(V,E_pi)$，其中 $E_pi={(v._pi,v):v\in V 且 v.\pi\neq NIL}$

除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每个结点有两个时间戳：第一个时间戳 $v.d$ 记录结点 $v$ 第一次被发现的时间，第二个时间戳 $v.f$ 记录的是搜索完成对 $v$ 邻接链表扫描对时间。这些时间戳提供了图结构对重要信息，能够帮助我们推断深度优先算法对行为。

深度优先搜索算法的伪代码如下：

DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.parent = NIL
    time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)

DFS-VISIT(G,u)
    time = time + 1
    u.d = time
    for each v in G.Adj[u]
        if v.color == WHITE
            v.parent = u
            DFS-VISIT(G, v)
    u.color = BLACK
    u.f = time

深度优先搜索算法的运行时间是 $\Theta (V+E)$

深度优先搜索的性质

深度优先搜索提供了很高价值的图结构信息。它生成的前驱子图$G_\pi$ 形成一个由多棵树所构成的森林，这是因为深度优先树的结构与 DFS-VISIT 的递归调用结构完全对应。 深度优先搜索的另一个重要性质是，结点的发现时间和完成时间具有所谓的 **括号化结构**。如 (s (z (x x) z) s). 深度优先搜索的另一个性质是，可以通过搜索来对输入图 $G=(V,E)$ 的边进行分类。**有向图是无环图当且仅当深度优先搜索不产生“后向边”**

对于深度优先森林，可以定义4种边：

  1. 树边：为深度优先森林$G_\pi$中的边。如果结点 $v$ 是因算法对边 $(u,v)$ 的探索而首先被发现的，则$(u,v)$是树边
  2. 后向边： 将结点 $u$ 连接到其在深度优先树中祖先结点 $v$ 的边。由于有向图中可以有自循环，自循环也被认为是后向边。
  3. 前向边：将结点 $u$ 连接到其在尝试优先树中一个后代结点 $v$ 的边 $(u,v)$
  4. 横向边：其他所有边。

当第一次探索 $(u,v)$ 结点时，结点 $v$ 的颜色能够告诉我们关于该条边的信息：

  1. 结点 $v$ 是白色表明该条边是树边
  2. 结点 $v$ 是灰色表明该边是一条后向边
  3. 结点 $v$ 是黒色表明该条边是一条前向边或横向边

拓扑排序

拓扑排序是用深度优先搜索来对有向无环图进行排序。 对于一个有向无环图 $G=(V,E)$ 来说，其拓扑排序是 $G$ 中所有结点的一种线性排序，该次序满足如下条件：如果图 $G$ 包含边 $(u,v)$，则结点 $u$ 的拓扑排序中处于结点 $v$ 的前面（如果图 $G$ 包含环路，则不可能排出一个线性次序）。可以将图的拓扑排序看做是将图的所有结点在一条水平线上排开。

拓扑排序用来指明有向无环图的优先次序。 其算法如下：

TOPOLOGICAL-SORT(G)
    call DFS(G) to compute finishing times v.f for each vertex v
    as each vertex is finished, insert it onto the front of a linked list
    return the linked list of vertices

强连通分量

如果一个无向图中每个定点从其他所有顶点都是可达的，则成该图是连通的。 如果一个有向图中任意两个定点相互可达，则该有向图是强连通的。对于有向图 $G=(V,E)$ 的强连通分量是一个最大结点集合 $C\subseteq V$，对于该集合中的任意一对结点 $u$ 和 $v$ 来说，路径 $u\rightarrow v$ 和路径 $v \rightarrow u$ 同时存在。

我们可以使用深度优先搜索算法来计算有向图的强连通分量，计算过程用用到了图 $G=(V,E)$ 的转置 $G=(V,E^T)$ , 这里 $E^T={(u,v):(v,u) \in E}$，即 $E^T$ 是对图 $G$ 中的边进行反转而获得。

下面的算法使用两次深度优先搜索来计算有向图 $G=(V,E)$ 的强连通分量，其运行时间为 $\Theta(V+E)$ :

STRONGLY-CONNECTED-COMPONENTS(G)
    call DFS(G) to compute finishing times u.f for each vertex u.
    compute G_T.
    call DFS(G_T), but int main loop of DFS, consider the vertices 
                in order of decreasing u.f (as computed in line 1).
    output the vertices of each tree in the depth-first forest formed in line 3 as 
                a separate strongly connected component.

上述算法来自于分量图 $G^{SOC} = (V^{SOC},E^{SOC})$ 的一个关键性质：假定图 $G$ 有强连通分量 $C_1, C_2, …, C_k$，结果集 $V^{SOC}={v_1,v_2,…,v_k}$。对于图 $G$ 的每个强连通分量来说，该集合包含代表该分量的结点 $v_i$。如果对于某个 $x\in C_i$ 和 $y\in C_j$, 图 $G$ 中包含一条有向边 $(x,y)$ 使得 $(v_i,v_j)\in E^{SOC}$。另一个角度看，通过收缩相邻结点都在同一个强连通分量中的边，剩下的就是图 $G^{SOC}$，该图是一个有向无环图。

最小生成树 – 无向图

对于一个连通的无向图 $G=(V,E)$ 的每条边 $(u,v)\in E$，为其赋予权重 $\omega(u,v)$ 作为从 $u$ 到 $v$ 的代价。希望找到一个无环子集 $T\subset E$，既能将所有的结点连接起来，又具有最小的权重，即 $\omega(T)=\sum_{(u,v)\in T}\omega(u,v)$ 的值最小。由于 $T$ 是无环的，并且连通所有结点，因此 $T$ 必然是一棵树，称其为生成树。我们称该问题为求图 $G$ 的最小生成树问题。

形成最小生成树

Kruskal算法和Prim算法都采用了贪心策略来形成最小生成树：该通用方法在每个时刻生长最小生成树的一条边，并在这个过程中，管理一个遵循下述循环不变式的边集合A: 在每遍循环之前，A是某棵最小生成树的一个子集 每一步选择一条边 $(u,v)$，将其加入到集合 $A$ 中， 使得 $A$ 不违指反循环不变式，即 $A\bigcup {(u,v)}$ 也是某棵最小生成树的子集。可以安全地将这种边加入到集合中，而不会破坏集合的循环不变式，因此称这样的边为集合 $A$ 的安全边。

无向图 $G=(V,E)$ 的一个切割 $(S,V-S)$ 是集合 $V$ 的一个划分，如果一条边 $(u,v)\in E$ 的一个端点位于集合 $S$，另一个商战位于集合 $V-S$，则称该条边横跨切割 $(S,V-S)$。如果集合 $A$ 中不存在横跨该切割的边，则称该切割尊重集合 $A$。在横跨一个切割的所有边中，权重最小的边称为轻量级边（轻量级边可能不唯一）。

定理：设 $G=(V,E)$ 是一个在边 $E$ 是定义了实数值权重函数 $\omega$ 的连通无向图。设 $A$ 为 $E$ 的一个子集，且 $A$ 包含在图 $G$ 的某棵最小生成树中，设 $(S,V-S)$ 是图 $G$ 中尊重集合 $A$ 的任意一个切割，又设$(u,v)$ 是横跨切割 $(S,V-S)$ 的一条轻量级边。那么边 $(u,v)$ 对于集合是安全的。

Kruskal 算法

Kruskal 算法中， 集合 $A$ 是一个森林，其结点就是给定图的结点，每次加入到集合 $A$ 中在安全边永远是权重最小的连接两个不同分量的边。 Kruskal算法找到安全边的办法是，在所有连接森林中两棵不同的树的边里面找到权重最小的边 $(u,v)$。设 $C_1$ 和 $C_2$ 是 $(u,v)$ 所连接的两棵树，边 $(u,v)$ 一定是连接 $C_1$ 和其他树的一条轻量级的边。

在Kruskal 算法中，我们使用一个不相交集合数据结构来维护几个互不相交的元素集合，每个集合代表当前森林中的一棵树。操作FIND-SET(u) 用来返回包含元素 u 在集合的代表元素，通过该方法判断结点 $u$ 和 $v$ 是否属于同一棵树。

MST-KRUSKAL(G, w) 
    A = {}
    for each vertex v in G.V
        MAKE-SET(v)
    sort the edages of G.E into nondecreasing order by weight w
    for each edge(u,v) in G.E, taken in nondecreasing order by weight
        if FIND-SET(v) != FIND-SET(u)
            A.add((u,v))
            UNION(u,v)
    return A

算法首先将集合 A 初始化为一个空集合，并创建 |V| 棵树，每棵树仅包含一个结点。将 G.E 从小到大排序，for 循环按照权重从低到高的次序对每条边逐一检查。对于每条边 $(u,v)$ 来说，该循环将检查端点 u 和 v 是否属于同一棵树。如果不是同一棵树，将这条边加入到集合中。

Prim 算法

Prim算法所具有的一个性质是集合 $A$ 中的边总是构成一棵树，这棵树从一个任意的根节点 r 开始，一直长大到覆盖 $V$ 中所有的结点为止。算法每一步在连接集合 $A$ 和 $A$ 之外的结点的所有边中，选择一条轻量级边加入到 $A$ 中。

为了有效实现Prim 算法，需要一种快速的方法来选择一条新的边，以便加入到有集合A中的边所构成的树里。在下面的伪代码中，连通图最小生成树的根节点 r 将作为算法的输入。执行过程中，所有不在树A中的结点都存放在一个基于key属性的最小优先队列Q中，对每个结点v，属性v.key保存的是连接v和树种结点的所有边种权重最小的边。如果不存在这样的边，则 $v.key=\infty$。属性v.parent是结点v在树中的父节点。

MST-PRIM(G,w,r)
    for each u in G.v
        u.key = Integer.MAX
        u.parent = NIL
    r.key = 0
    Q = G.V
    while Q.size() != 0 
        u = EXTRACT-MIN(Q)
        for each v in G.Adj[u]
            if v in Q and w(u,v) < v.key
                v.parent = u
                v.key = w(u,v)

单源最短路径

最短路径问题 给定一个带权重的有向图 $G=(V,E)$ 和权重函数 $\omega: E \rightarrow R$，该权重函数将每条边映射到实数值的权重上。图中一条路径 $p=(v_0, v_1, … , v_k)$ 的权重 $\omega(p)$ 是构成该路径的所有边的权重之和： $$ \omega(p)=\sum_{i=1}^k \omega(v_{i-1}, v_i)$$ 定义从结点 $u$ 到结点 $v$ 的最短路径 $\delta(u,v)$ 如下： $$\delta(u,v)=\left\{ \begin{array}{ll} \min\{\omega(p)\}& \textrm{如果存在一条从u到v的路径}\\ \infty & \textrm{其他} \end{array} \right. $$

环路问题

某些单源最短路径可能包括权重为负值的边，但是如果包含总权重为负值的环路，那么最短路径权重没有意义。因为我们只要沿着总权重为负值的环路再走一遍，就可以找到权重更小的路径，如果包含总权重为负值的环路，那么我们定义 $\theta(s,v)=-\infty$

最短路径中也不会包含总权重大于0的环路，因为只要把环路去掉，总会有更小的权重。

最短路径表示

给定图 $G=(V,E)$，对于每个结点 $v$，我们维持一个前驱结点 $v_\pi$。该前驱结点可能是另一个结点或者NIL，计算时只要将前驱结点链反转过来，就是从$s$ 到 $v$ 的一条最短路径。

在运行最短路径算法的过程中， $\pi$ 值不一定能给出最短路径，我们所感兴趣的是 $\pi$ 值所诱导的前驱子图 $G_\pi=(V_\pi,E_\pi)$。定义结点集 $V_\pi$ 为图 $G$ 中的前驱结点不为NIL的结点集合，再加上源节点 $s$： $$V_\pi =\{v in V:v_\pi \neq NIL\} \bigcup \{s\}$$ 有向边集合 $E_\pi$ 是由 $V_\pi$ 中的结点 $\pi$ 值所诱导的边的集合： $$E_\pi =\{(v_\pi,v) \in E:v \in V_\pi - \{s\}\}$$

最短路径树是一棵有根结点的树，该树包括了从源节点到每个可以从源节点叨叨的结点的一条最短路径。

松弛操作

对于每个结点 $v$，维持一个属性 v.d，来记录从源节点到结点 $v$ 的最短路径权重上界。以下算法用来初始化：

INITIALIZE-SINGLE-SOURCE(G,s)
    for each vertex v in G.V
        v.d = ∞
        v.parent= NIL
    s.d = 0

对一条表 $(u,v)$ 的 松弛 过程为：测试以下是否可以从 $s$ 到 $v$ 的最短路径进行改善。具体测试方法是：将从几点 $s$ 到结点 $v$ 之间的最短路径距离加上结点 $u$ 与 $v$ 之间的边的权重，并与当前的最短路径估计进行比较，取较小者。

RELAX(u,v,w) 
    if v.d > u.d + w(u,v)
        v.d = u.d + w(u,v)
        v.parent = u

单源最短路径不同算法之间是对每条边进行松弛的次数和松弛边的次序有所不同。Dijkstra算法和用于有向无环图的最短路径算法对每条边仅松弛一次。Bellman-Ford算法则对每条边松弛 $|V|-1$ 次。

最短路径和松弛操作性质

三角不等式性质： 对于任何边 $(v,e) \in E$，我们有 $\theta(s,v) \leq \theta(s,u) + \omega(u,v)$

上界性质：对于所有结点 $v \in V$，我们总是有 $v.d \geq \theta(s,v)$.

非路径性质：如果从结点 $s$ 到结点 $v$ 之间不存在路径，则总是有 $v.d=\theta(s,v)=\infty$

收敛性质：对于某些结点 $u,v \in V$，如果 $s\leftarrow u \leftarrow v$ 是图中的一条最短路径，并且在对边 $(u,v)$进行松弛前的任意时间有 $u.d=\theta(s,u)$，则在之后的时间有 $v.d=\theta(s,v)$

前驱子图性质：对于所有结点 $v\in V$，一旦 $v.d=\theta(s,v)$，则前驱子图是一棵根节点为 $s$ 的最短路径树。

Bellman-Ford 算法

Bellman-Ford算法允许边的权重为负值，运行时间为 $O(VE)$。给定带权重的有向图和权重函数，Bellman-Ford算法返回一个布尔值，以表明是否存在一个从源节点达到权重为负值的环路。算法运行完毕后，可以根据结点中的 parent 构建最短路径树。

BELLMAN-FORD(G,w,s)
    INITIALIZE-SINGLE-SOURCE(G,s)
    // 算法对图的每条边进行 |V| - 1 次松弛操作
    for i=1 to |G.V|-1
        for each edge(u,v) in G.E
            RELAX(u,v,w)
    // 检查是否存在权重为负值的环路，并返回相应布尔值
    for each edge(u,v) in G.E
        if (v.d > u.d + w(u,v))
            return FALSE
    return TRUE

有向无环图中的单源最短路径问题

根据结点的拓扑排序次序来对带权重的有向无环图 $G=(V,E)$ 进行边的松弛操作，可以在 $\Theta(V+E)$ 时间内计算出从单个源结点到所有结点之间的最短路径。因为无环，所以不存在权重为负值的环路。 先对有向无环图进行拓扑排序，以确定结点间的一个线性次序。如果有向无环图包含从结点 $u$ 到 $v$ 的一条路径，则 $u$ 的拓扑排序的次序位于结点 $v$ 的前面。我们只需要按照拓扑排序的次序对结点进行一遍处理即可。

DAG-SHORTEST-PATHS(G,w,s)
    topologically sort the vertices of G
    INITIALIZE-SINGLE-SOURCE(G,s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            RELAX(u,v,w)

如果带权重的无环路的有向图 $G=(V,E)$ 有一个源节点 $s$，则在算法DAG-SHORTEST-PATHS结束时，对于所有点 $v$，我们有 $v.d=\theta(s,v)$，且前驱子图 $G_\pi$ 时一棵最短路径树。

Dijkstra 算法

Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有便的权重都为非负值。 Dijkstra 算法在运行过程中维持的关键信息是一组结点集合 $S$，从源节点 $s$ 到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集 $V-S$ 中选择最短路径估计最小的结点 $u$，将 $u$加入到集合 $S$ 中，然后对所有从 $u$ 出发的边进行松弛。

DIJKSTRA(G,w,s)
    INITIALIZE-SINGLE-SOURCE(G,s)
    S = {}
    Q = G.V
    while Q.size() > 0
        u = EXTRACT-MIN(Q)
        S.add(u)
        for each vertex v in G.Adj[u]
            RELAX(u,v,w) 
            // 重构队列，需要修改v所在的队列位置

所有结点对的最短路径

如何找到一个图中所有结点之间的最短路径？ 给定一个带权重的有向图 $G=(V,E)$，其权重函数为 $\omega: E\rightarrow R$，该函数将边映射到实数值的权重上。我们希望找到，对于所有结点对 $u,v \in V$，一条结点 $u$ 到结点 $v$ 的最短路径，其中一条路径的权重为组成该路径的所有边的权重之和。通常以表格的形式给出：第u行第v列是结点$u$到结点$v$的最短路径权重。

与单源最短路径不同，计算所有结点的最短路径时使用邻接矩阵的方式表示图。假定结点的编号是 $1,2,3…,|V|$，因此，算法的输入将是一个 $n*n$ 的矩阵 $W$，该矩阵代表的是一个有n个结点的有向图 $G=(v,E)$ 的边的权重。

为了解决所有结点对最短路径问题，我们还需要计算出前驱结点矩阵 $\Pi=(\pi_{ij})$，其中 $\pi_{ij}$ 在 $i=j$ 或从$i$到$j$不存在路径是为 NIL，其他情况下是从$i$到$j$的某条最短路径上结点$j$ 的前驱结点。

首先要对邻接矩阵的表示给出一些约定。假定输入图 $G=(V,E)$ 有 $n$ 个结点，因此$n=|V|$。其次使用大写字母来表示矩阵，如 $W,L,D$ 等，用小写字母来表示矩阵中的个体元素，如 $\omega_{ij}, l_{ij},d_{ij}$等。$L^{(m)}=(l_{ij}^{(m)})$ 或 $D^{(m)}=(d_{ij}^{(m)})$ 用来表示迭代。

最短路径和矩阵乘法

有向图上所有结点对的最短路径问题，有一种动态规划算法：

最短路径结构

因为一条最短路径的所有子路径都是最短路径，考虑从结点 $i$ 到 $j$的一条最短路径 $p$，假定 $p$ 最多包含 $m$ 条边，还要假定没有权重为负值的环路，且 $m$ 为有限值。如果 $i=j$ ，则 $p$ 的权重为0且不包含任何边。如果结点 $i\neq j$，则路径可以分解为 $i\rightarrow k\rightarrow j$，那么 $\theta(i,j)=\theta(i,k)+\omega_{kj}$

所有结点对最短路径问题的递归

现在设 $l_{ij}^{(m)}$ 是从结点 $i$ 到 $j$ 的至多包含 m 条边的任意路径找那个的最小权重。 那么当 $m=0$时，即从结点 $i$ 到 $j$没有最短路径： $$l_{ij}^{(m)}=\left\{ \begin{array}{ll} 0& \textrm{if $i=j$}\\ \infty & \textrm{if $i\neq j$} \end{array} \right. $$

对于 $m\geq 1$，需要计算的 $l_{ij}^{(m)}$ 是 $l_{ij}^{(m-1)}$ 的最小值和从 $i$ 到 $j$ 最多由 $m$ 条边组成的任意路径的最小权重。通过对 $j$ 所有可能前驱 $k$ 进行检查来获得该值： $$l_{ij}^{(m)}=\min\left(l_{ij}^{(m-1)}, \min_{1\leq k\leq n} \left\{ l_{ik}^{(m-1)} + \omega_{kj}\right\} \right) = min_{1\leq k\leq n} \left\{ l_{ik}^{(m-1)} + \omega_{kj}\right\}$$

因为从结点 $i$ 到 $j$ 的由多于 $n-1$ 条边构成的路径不可能有比从 $i$ 到 $j$的最短路径权重更小的权重，因此，真正的最短路径可以由下面的公式给出： $$\theta(i,j) = l_{ij}^(n-1) = l_{ij}^{(n)} = l_{ij}^{(n+1)} = ...$$

自底向上计算最短路径权重

根据输入矩阵 $W=(\omega_{ij})$，现可以计算矩阵序列 $L^{(1)},L^{(2)},…,L^{(n-1)}$，对于 $m=1,2,…,n-1$，有 $L^{(m)}=\left(l_{ij}^{(m)}\right)$。最后的矩阵 $L^{(n-1)}$ 包含的是最短路径的实际权重。

该算法的核心是在给定 $W$ 和 $L^{(m-1)}$ 的情况下，计算出 $L^{(m)}$。也就是说该伪代码将最近计算出的最短路径扩展了一条边。

EXTEND-SHORTTEST-PATHS(L,W)
    n = L.rows
    let _L be new n*n array
    for i=1 to n
        for j=1 to n
            _L[i][j] = ∞
            for k=1 to n
                _L[i][j] = min(_L[i][j], L[i][k] + W[k][j])
    return _L

下面的伪代码在 $\Theta(n^4)$时间内计算出该矩阵序列

SHOW-ALL-PARITS-SHORTEST-PATHS(W)
    n = W.rows
    L_1 = W
    for n=2 to n-1
        L_m be a new n*n array
        L_m = EXTEND-SHORTTEST-PATHS(L_(m-1), W)
    return L_(n-1)

在权重都为非负值的环路情况下，可以使用重复平方技术来计算上述矩阵序列

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
    n = W.rows
    L_1 = W
    m = 1
    while m < n-1
        let L_2m be a new n*n array
        L_2m = EXTEND-SHORTTEST-PATHS(L_m, L_m)
        m = 2m
    return L_m

Floyd-Warshall 算法

Floyd-Warshall 算法的运行时间为 $\Theta(V^3)$，其前提假设是 可以有负权重的边，但是不能有权重为负的环路.

假定图 $G$ 的所有结点为 $V={1,2,…,n}$，其中的一个子集 ${1,2,…,k}$，这里 $k\lt n$。对于任意结点 $i,j \in V$，考虑从结点$i$到结点$j$的所有中间结点均取自集合 ${1,2,…,k}$ 的路径，并假设 $p$ 是其中权重最小的路径。

  • 如果结点 $k$ 不是路径 $p$ 上的中间结点，则路径 $p$ 上所有的中间结点都属于集合 ${1,2,…,k-1}$。因此从结点 $i$ 到结点 $j$ 的中间结点取自集合 ${1,2,…,k-1}$ 的一条最短路径也是从结点$i$ 到结点 $j$ 的中间结点取自集合 ${1,2,…,k}$ 的一条最短路径
  • 如果结点 $k$ 是路径 $p$ 上的中间结点，则将路径 $p$ 分解为 $i\rightarrow k \rightarrow j$。因为结点$k$不是路径 $p_1$ 上的中间结点，路径 $p_1$ 上的所有中间结点都属于集合${1,2,…,k-1}$，所以 $p_1$ 是从结点 $i$ 到结点 $k$ 的中间结点全部曲子集合 ${1,2,…,k-1}$ 的一条最短路径

基于上述观察，可以定义一个最短路径估计的递归公式。

假设 $d_{ij}^{(k)}$ 为从结点 $i$ 到 $j$ 的所有中间结点全部取自集合 ${1,2,…,k}$ 的一条最短路径的权重，当 $k=0$ 时，从结点 $i$ 到结点 $j$ 的一条不包括编号大于 0 的中间结点的路径将没有任何中间结点。这样的路径最多只有一条边。因此对于 ${1,2,…,k}$， $\omega_{ij}$，$d_{ij}^{(k)}$的递归定义如下： $$d_{ij}^{(k)}=\left\{ \begin{array}{ll} \omega_{ij} & \textrm{if $k=0$}\\ \min\left( d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \right) & \textrm{if $k\geq 1$} \end{array} \right. $$

对于任何路径来说，所有的中间结点都属于集合 ${1,2,…,n}$ ，矩阵 $D^{(n)} = d_{ij}^{(n)}$ 给出的就是最后的答案。

自底向上计算最短路径权重的伪代码如下：

FLOYD-WARSHALL(W)
    n = W.rows
    D_0 = W
    for k = 1 to n
        let D_k be a new n*n array
        for i = 1 to n
            for j = 1 to n
                D_k[i][j] = min(D_(k-1)[i][j], D_(k-1)[i][k] + D_(k-1)[k][j])
    return D_n

构造一条最短路径 可以在计算最短路径权重 $D$ 之后，根据 $D$ 来构造前驱矩阵。也可以在构造 $D$ 时，一起构造前驱矩阵。 计算一个矩阵序列 $\Pi^{(0)}, \Pi^{(1)},…,\Pi^{(n)}$，这里 $\Pi=\Pi^{(n)}$，且定义 $\pi_{ij}^{(k)}$ 为从结点 $i$ 到 $j$ 的一条所有中间节点都取自集合 ${1,2,…,k}$ 的最短路径上 $j$ 的前驱结点。

下面给出了 $\pi_{ij}^{(k)}$ 的递归公式 $$\pi_{ij}^{(k)}=\left\{ \begin{array}{ll} NIL & \textrm{if $i=j or \omega_{ij}=\infty$}\\ i & \textrm{if $i\neq j and \omega_{ij}\lt\infty$} \end{array} \right. $$

local_offer #算法 
navigate_before navigate_next