Chapter 8 - Graph-Shortest Paths

Hare Fuyukawa Lv4
  2026-05-04 15:12:07 2026-05-04 15:12:07 Created   2026-06-03 17:38:49 2026-06-03 17:38:49 Updated    

定义

注意

补充、解释

其他

1 Shortest Paths


如果图中存在负权环（环上所有边的代价之和为负数），则最短路径不存在 —— 因为可以绕环无限次，让路径长度无限减小。
若图中无负权环，定义源点到自身的最短路径长度为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Unweighted(Table T) {
    int CurrDist;
    Vertex V, W;
    // 按距离从小到大处理所有顶点
    for (CurrDist = 0; CurrDist < NumVertex; CurrDist++) {
        // 找到所有距离为CurrDist且未处理的顶点
        for (each vertex V) {
            if (!T[V].Known && T[V].Dist == CurrDist) {
                T[V].Known = true;
                // 更新邻接点的距离
                for (each W adjacent to V) {
                    if (T[W].Dist == Infinity) {
                        T[W].Dist = CurrDist + 1;
                        T[W].Path = V;
                    }
                }
            }
        }
    }
}

初始状态：T[v3].Dist = 0，其他顶点的 Dist = Infinity，所有 Known = false。
CurrDist = 0：
中间循环扫所有顶点，找到 Dist=0 且 Known=false 的 v3。
把 T[v3].Known 设为 true。
看 v3 的邻接点（比如 v1、v6），它们的 Dist 是 Infinity，所以：
T[v1].Dist = 0+1 = 1，T[v1].Path = v3；
T[v6].Dist = 0+1 = 1，T[v6].Path = v3。
CurrDist = 1：
中间循环扫所有顶点，找到 Dist=1 且 Known=false 的 v1 和 v6。
先处理 v1：标记为 Known=true，看它的邻接点 v2、v4，把它们的 Dist 设为 1+1=2，Path 设为 v1。
再处理 v6：同理标记并更新它的邻接点。
CurrDist = 2：
找到 v2、v4，处理它们的邻接点 v5、v7，把距离设为 3。

CurrDist其实就代表了是第几层，本质上就是广度优先搜索

但是对于一条链，比如

找dist为0的点，遍历一遍，找到
找dist为1的点，遍历一遍，找到
找dist为2的点，遍历一遍，找到
…
所以复杂度是，太大了

优化：使用队列，对于每一层的每个顶点，把它的下一层，即它邻接的点入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Unweighted(Table T) {
    Queue Q;
    Vertex V, W;
    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    Enqueue(S, Q); // 源点入队，源点的Dist是0

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        T[V].Known = true; // 此标记非必需，因为每个顶点仅入队一次
        // 更新所有未访问的邻接点
        for (each W adjacent to V) {
            if (T[W].Dist == Infinity) {
                T[W].Dist = T[V].Dist + 1;
                T[W].Path = V;
                Enqueue(W, Q);
            }
        }
    }
    DisposeQueue(Q);
}

时间复杂度为（每个顶点入队 / 出队 1 次，每条边被处理 1 次）

2 Dijkstra’s Algorithm

这是最经典的带权图最短路径算法，基于贪心策略，要求所有边的权值非负。

  • 定义集合 ：包含源点 和所有已经找到最短路径的顶点。
  • 对于不在 中的顶点 ，定义 distance[u]：从 出发，只经过 中的顶点到达 的最短路径长度。
  • 算法步骤：
    1. 初始化 ，distance[s]=0，其他顶点为无穷大。
    2. 重复直到 包含所有顶点：
      • 选择不在 中且 distance 最小的顶点 ，加入 （贪心选择）。
      • 对 的每个邻接点 ，更新 distance[v] = min(distance[v], distance[u]+c(u,v))。

证明
假设选择 加入 时，distance[u] 其实不是 到 的最短路径长度。那么存在一条更短的路径 ，其中 不在 中，否则这条路径长度肯定小于等于 distance[u]。此时 distance[w] < distance[u]，与” 是不在 中距离最小的顶点”矛盾。因此贪心选择是正确的。

伪代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dijkstra(Table T) {
    Vertex V, W;
    for (;;) {
        // 找到距离最小的未处理顶点
        V = smallest unknown distance vertex;
        if (V == NotAVertex) break; // 所有顶点处理完毕

        T[V].Known = true;
        // 更新所有邻接点的距离
        for (each W adjacent to V) {
            if (!T[W].Known) {
                if (T[V].Dist + Cvw < T[W].Dist) {
                    T[W].Dist = T[V].Dist + Cvw;
                    T[W].Path = V;
                }
            }
        }
    }
}

例如
带权图结构：

算法执行过程：

  1. 初始：v1.Dist=0，其他为∞。选v1加入S，更新v2.Dist=2，v4.Dist=1。
  2. 选v4（最小未处理）加入S，更新v3.Dist=3，v5.Dist=3，v6.Dist=9，v7.Dist=5。
  3. 选v2（最小未处理）加入S，v5当前Dist=3 < 2+10=12，不更新。
  4. 选v3（最小未处理）加入S，更新v6.Dist=min(9,3+5)=8。
  5. 选v5（最小未处理）加入S，v7当前Dist=5 < 3+6=9，不更新。
  6. 选v7（最小未处理）加入S，更新v6.Dist=min(8,5+1)=6。
  7. 选v6加入S，算法结束。

2.1 Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define Infinity INT_MAX  // 用int最大值表示无穷大
#define NotAVertex -1     // 表示没有找到顶点
#define MaxVertexNum 100  // 最大顶点数

// PPT里的Table结构体，一字不差对应三个字段
typedef struct {
    int Dist;    // 源点到该顶点的最短距离
    int Known;   // 是否已加入S集合（0=未加入，1=已加入）
    int Path;    // 前驱顶点编号（用于打印路径）
} TableEntry;

typedef TableEntry Table[MaxVertexNum];  // Table是结构体数组
typedef int Vertex;                      // 顶点用整数编号（0~n-1）
typedef int Weight;                      // 边权用整数表示

// 邻接表表示图（PPT里的图用邻接表存储最方便）
typedef struct AdjNode {
    Vertex adjvex;          // 邻接点编号
    Weight weight;          // 边的权值
    struct AdjNode *next;   // 下一个邻接点
} AdjNode;

typedef struct {
    AdjNode *head[MaxVertexNum];  // 每个顶点的邻接表头
    int vertexNum;                // 顶点总数
    int edgeNum;                  // 边总数
} Graph;

// 初始化Table数组（PPT要求的初始化方式）
void InitTable(Vertex start, Graph *G, Table T) {
    for (int i = 0; i < G->vertexNum; i++) {
        T[i].Dist = Infinity;
        T[i].Known = 0;
        T[i].Path = NotAVertex;
    }
    T[start].Dist = 0;  // 源点距离为0
}

// 核心：找到距离最小的未处理顶点（PPT里的V = smallest unknown distance vertex）
Vertex FindMinDist(Table T, Graph *G) {
    int minDist = Infinity;
    Vertex minV = NotAVertex;
    // 暴力扫描所有顶点（这就是基础版的核心）
    for (int i = 0; i < G->vertexNum; i++) {
        if (!T[i].Known && T[i].Dist < minDist) {
            minDist = T[i].Dist;
            minV = i;
        }
    }
    return minV;
}

// PPT第6页的Dijkstra伪代码的C语言实现
void Dijkstra_Basic(Graph *G, Vertex start, Table T) {
    InitTable(start, G, T);
    Vertex V, W;
    AdjNode *p;

    for (;;) {  // 对应PPT里的for(;;)循环
        // 步骤1：找最小距离的未处理顶点
        V = FindMinDist(T, G);
        if (V == NotAVertex) break;  // 所有顶点处理完毕，退出

        // 步骤2：将V加入S集合
        T[V].Known = 1;

        // 步骤3：遍历V的所有邻接点，更新距离
        p = G->head[V];
        while (p != NULL) {
            W = p->adjvex;
            if (!T[W].Known) {  // 只更新未加入S的顶点
                // 松弛操作：如果经过V到W更短，就更新
                if (T[V].Dist + p->weight < T[W].Dist) {
                    T[W].Dist = T[V].Dist + p->weight;
                    T[W].Path = V;  // 记录前驱
                }
            }
            p = p->next;
        }
    }
}

外层循环执行 | V | 次（每个顶点处理 1 次）
每次FindMinDist是 O (|V|)
所有边总共被处理 1 次（O (|E|)）
总时间：
（稠密图中 | E|≈|V|²，这个复杂度是最优的）

可以用堆来优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 优先队列元素：(距离, 顶点编号)
typedef struct {
    int dist;
    Vertex v;
} PQNode;

// 最小堆实现（简化版，只实现必要操作）
typedef struct {
    PQNode data[MaxVertexNum * 10];  // 足够大的空间存重复条目
    int size;
} MinHeap;

// 堆的插入操作（O(logn)）
void InsertHeap(MinHeap *heap, int dist, Vertex v) {
    int i = ++heap->size;
    while (i > 1 && dist < heap->data[i/2].dist) {
        heap->data[i] = heap->data[i/2];
        i /= 2;
    }
    heap->data[i].dist = dist;
    heap->data[i].v = v;
}

// 堆的删除最小值操作（O(logn)）
PQNode DeleteMin(MinHeap *heap) {
    PQNode minNode = heap->data[1];
    PQNode lastNode = heap->data[heap->size--];
    int i = 1, child;
    while (i * 2 <= heap->size) {
        child = i * 2;
        if (child != heap->size && heap->data[child+1].dist < heap->data[child].dist)
            child++;
        if (lastNode.dist <= heap->data[child].dist)
            break;
        heap->data[i] = heap->data[child];
        i = child;
    }
    heap->data[i] = lastNode;
    return minNode;
}

// 优先队列版Dijkstra
void Dijkstra_PriorityQueue(Graph *G, Vertex start, Table T) {
    InitTable(start, G, T);
    MinHeap heap;
    heap.size = 0;
    InsertHeap(&heap, 0, start);  // 源点入堆

    Vertex V, W;
    AdjNode *p;
    PQNode node;

    while (heap.size > 0) {
        // 步骤1：取出距离最小的顶点
        node = DeleteMin(&heap);
        V = node.v;
        if (T[V].Known) continue;  // 关键：如果已经处理过，直接跳过

        // 步骤2：标记为已处理
        T[V].Known = 1;

        // 步骤3：更新邻接点
        p = G->head[V];
        while (p != NULL) {
            W = p->adjvex;
            if (!T[W].Known && T[V].Dist + p->weight < T[W].Dist) {
                T[W].Dist = T[V].Dist + p->weight;
                T[W].Path = V;
                InsertHeap(&heap, T[W].Dist, W);  // 插入新条目到堆中
            }
            p = p->next;
        }
    }
}

更新时，我们把更新后的元素插入到堆中，最多可能要更新次，每次插入需要为堆中元素个数，由于Dijkstra算法对于每条边只会插入堆一次，所以堆中元素最多个，而²，故总时间复杂度为

3 Graph With Negative Edge Costs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void WeightedNegative(Table T) {
    Queue Q;
    Vertex V, W;
    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    Enqueue(S, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        for (each W adjacent to V) {
            if (T[V].Dist + Cvw < T[W].Dist) {
                T[W].Dist = T[V].Dist + Cvw;
                T[W].Path = V;
                if (W不在队列中) {
                    Enqueue(W, Q);
                }
            }
        }
    }
    DisposeQueue(Q);
}

该算法(SPFA)的思路是，从源点开始，每次检查所有边需不需要更新，核心就在于负权边并不是像Dijsktra算法一样当前最短就能直接视为最短路径了，每次更新都要检查，SPFA 的队列允许一个人反复进出。只要你拿到了更短的距离，不管你之前进过几次队列，你都可以重新排队


如上图，左边的图中，A先入队，然后出队，更新A到C是3，A到B是2，按Dijkstra算法，B就会被认为已经找到了最短路径。
接下来B,C入队，B出队，没有能到达的，C出队，D入队，A到D更新成-3，D出队，更新A到B是-5，B入队；B出队，没有更新的，队空，结束。这时A到B,C,D的最短路是-5，3，-3，正确！

而上图右边的图，A先入队，然后出队，C入队；C出队，D入队；D出队，B入队；B出队，A入队……循环不会停止

怎么避免这种循环不停的情况呢？一条非环的最短路径最多V-1条边，对于一个顶点B，从A到B最多V-1条边，每次更新相当于在原有的路上又多加了一条边，所以一个顶点最多入队V-1次，若入队V次说明有环，如果是0或正的环，不会入队的，所以一定是负权环，所以只需要记录每个顶点入队次数就可以检验

每个顶点最多入队V次（为了检验负权环情况，最多V次），时间复杂度为

4 Acyclic Graphs & AOE

If the graph is directed and acyclic, vertices may be selected in topological order since when a vertex is selected, its distance can no longer be lowered without any incoming edges from unknown nodes.

对于有向无环图，按拓扑排序去遍历，到某个顶点时，指向这个顶点的路径已经“没”了，所以此时的dist就是最小的了

  1. 计算所有顶点的入度。
  2. 将入度为 0 的顶点放入队列。
  3. 取出顶点 ，遍历其邻居 ：更新距离：if (dist[V] + Cvw < dist[W]) dist[W] = dist[V] + Cvw;
  4. 将 的入度减 1，若减为 0 则将 入队。

4.1 AOE


假设有这么一个项目，边称作活动，顶点称作事件，每个事件必须在前一个指向它的事件做完后才可以开始做，求完成这个项目的最短时间
活动可以同时进行，所以时间取决于最耗时的那条路，称作关键路径
关键活动：不能拖延的活动，即该活动的最早开始时间和最晚开始时间一样
我们先看0到4，上面那条路要7，下面是5，所以上面那条路是关键路径，而活动1的最早开始时间当然是第0天，最晚开始时间是第2天，因为这样2+4+1=7刚好跟上面的路同步完成。或者说，事件2的最早完成时间是第4天，最晚完成时间是第6天

  • Title: Chapter 8 - Graph-Shortest Paths
  • Author: Hare Fuyukawa
  • Created at : 2026-05-04 15:12:07
  • Updated at : 2026-06-03 17:38:49
  • Link: https://redefine.ohevan.com/Data-Structure/DS/FDS-9/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Chapter 8 - Graph-Shortest Paths
  1. 1 Shortest Paths
  2. 2 Dijkstra’s Algorithm
    1. 2.1 Implementation
  3. 3 Graph With Negative Edge Costs
  4. 4 Acyclic Graphs & AOE
    1. 4.1 AOE