5.3.3 最短路径

原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 5.3.3 最短路径

## 无权图

对于无权图（其实也可以用于权值相同的图），最短路径是指从一个顶点到另一个顶点经过的边数最少的路径。由于每条边的“权重”可以视为1，我们可以使用广度优先搜索（BFS）来寻找最短路径。BFS按层级遍历图，天然地保证了最先到达某个顶点的路径就是最短路径。

思路：使用广度优先搜索（BFS）。从源点开始，逐层向外扩展，第一次访问到某个顶点时，所经过的路径就是从源点到该顶点的最短路径。

步骤：

1. 初始化距离数组 dist，dist[start] = 0，所有其他顶点的距离为无穷大 ∞。同时，初始化路径数组path 用于记录前驱结点。

2. 创建一个队列，并将源点 start 入队。

3. 队列不为空则循环执行：

a. 从队头取出一个顶点 u。

b. 遍历 u 的所有邻接点 v。如果 v 尚未入队则将 v 入队并更新距离。

\*邻接矩阵代码如下，时间复杂度为O(n²):

<!-- verified-by-hand -->
> [!success] 已结合原文第 143 页及 Markdown 上下文人工校对
> 初始化源点和 BFS 主循环被错嵌进初始化 for；数组声明及注释也被 OCR 损坏。
void BFS_ShortestPath(MGraph G, int start)
{
    int queue[MAXV], visited[MAXV] = {false};
    int dist[MAXV], path[MAXV];
    int front = 0, rear = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[start] = 0;
    queue[rear++] = start;
    visited[start] = true;
    while (front &lt; rear)
    {
        int u = queue[front++];
        for (int v = 0; v &lt; G.numVertices; v++)
            if (!visited[v] &amp;&amp; G.Edge[u][v] == 1)
            {
                dist[v] = dist[u] + 1;
                path[v] = u;
                queue[rear++] = v;
                visited[v] = true;
            }
    }
    // 根据 dist 数组输出长度，根据 path 数组输出路径
}


<!-- page 144 -->

如果 dist[v] 为无穷大，就说明未访问过，因此它可以实现 visited 数组的功能，后者是冗余的。所以其实可以基于上面的代码进一步改写。

邻接表代码如下，时间复杂度为O(n+e):

<!-- verified-by-hand -->
> [!success] 已结合原文第 144 页及 Markdown 上下文人工校对
> 按 BFS 单源最短路标准流程及本页分步注释校正：将源点入队和 BFS 主循环移出初始化 for，补 ArcNode 指针声明
void BFS_ShortestPath_AL(ALGraph G, int start)
{
    int queue[MAXV];
    int dist[MAXV], path[MAXV];
    int front = 0, rear = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[start] = 0;
    queue[rear++] = start;
    while (front &lt; rear)
    {
        int u = queue[front++];
        ArcNode *p = G.VerticesList[u].first;
        while (p != NULL)
        {
            int v = p-&gt;adjvex;
            if (dist[v] == INT_MAX)
            {
                dist[v] = dist[u] + 1;
                path[v] = u;
                queue[rear++] = v;
            }
            p = p-&gt;next;
        }
    }
    // 根据 dist 数组输出长度，根据 path 数组输出路径
}


<!-- page 145 -->

## 有权图-Dijsktra算法

在一个有权图中，我们要求从一个点出发到达其他所有点需要花费的时间。把这个过程想象成在一张地图上找从你家（起点）到所有其他地方的最短花费时间。

## 1. 准备阶段（初始化）

。在你家旁边标注“用时0分钟”。

。在所有其他地点旁边都标注“用时无限长”，因为你还不知道怎么去。

。你再准备一个集合，叫做“已确定最短时间的地点”，开始时为空。

## 2. 核心循环(不断寻找下一个最近的地点）

算法会不断重复以下步骤，直到所有地点都被你“确定”下来:

。第一步：选择

从所有尚未确定的地点中，挑选一个当前记录用时最短的地点。第一次挑选时，肯定是你家（用时0分钟）。

。第二步：确定

当你检查完所有从A点出发能到的邻近地点后，你就把“A点”加入“已确定最短时间的地点”集合中，之后不再考察它。

。第三步：更新

现在，你站在刚选出的这个地点（比如叫“A点”），看看从A点能直接开车到哪些尚未确定的邻近地点（比如“B点”）。

你计算一下“从你家开到A点的时间”+“从A点开到B点的时间”，看看这个总时间是否比你清单上记录的到达B点的用时更短。如果更短，你就在清单上更新到达B点的用时。

当你把地图上所有能到达的地点都加入了“已确定”集合后，算法就结束了。这时，你清单上记录的就是从你家到每个
地点的最短驾车时间。W

这个算法的精髓（贪心策略）在于：每次都选择当前看起来最近的那个点，并认定它的最短路径已经找到，然后用它来更新其他邻居点的路径。

从已知世界S扩展到未知世界，每次都选择距离源点最近的：

<!-- page 146 -->

(b)

(c)

(d)


(f)

步骤:

1. 初始化。初始化距离数组 dist，dist[s] = 0，所有其他顶点的距离为无穷大 ∞。同时，初始化路径数组path 用于记录前驱结点。

2. 循环直到所有顶点都已确定：

a. 每次选择距离dist 最小的、未选择过已确定顶点u。

b. 将顶点u 视为已确定的顶点，之后不再考虑。

c. 将 u 出发的所有邻接点 ν 做松弛：

if (dist[u] + w(u,v) &lt; dist[v])
dist[v] = dist[u] + w(u,v)


邻接矩阵代码如下，时间复杂度为O(n²):

<!-- verified-by-hand -->
> [!success] 已结合原文第 146 页及 Markdown 上下文人工校对
> 初始化与外层循环错嵌，u 声明失去作用域，缺少不可达保护且 return 提前。
void Dijkstra(MGraph G, int start)
{
    int dist[MAXV], path[MAXV];
    bool visited[MAXV] = {false};
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[start] = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int u = -1, min_dist = INT_MAX;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (!visited[j] &amp;&amp; dist[j] &lt; min_dist)
            {
                min_dist = dist[j];
                u = j;
            }
        if (u == -1) break;
        visited[u] = true;
        for (int v = 0; v &lt; G.numVertices; v++)
            if (!visited[v] &amp;&amp; G.Edge[u][v] != 0 &amp;&amp; dist[u] != INT_MAX &amp;&amp; dist[u] + G.Edge[u][v] &lt; dist[v])
            {
                dist[v] = dist[u] + G.Edge[u][v];
                path[v] = u;
            }
    }
    // 根据 dist 数组输出长度，根据 path 数组输出路径
}


<!-- page 147 -->

请大家思考一个问题，Dijsktra 算法中的 visited 数组能否删去？为什么？

邻接表代码如下，时间复杂度为O(n²):

<!-- verified-by-hand -->
> [!success] 已结合原文第 147-148 页及 Markdown 上下文人工校对
> 函数被分页拆成两块，且选点后的判断、访问和松弛被错嵌进扫描 j 的循环。
void Dijkstra_AL(ALGraph G, int start)
{
    int dist[MAXV], path[MAXV];
    bool visited[MAXV] = {false};
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[start] = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int u = -1, min_dist = INT_MAX;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (!visited[j] &amp;&amp; dist[j] &lt; min_dist)
            {
                min_dist = dist[j];
                u = j;
            }
        if (u == -1) break;
        visited[u] = true;
        for (ArcNode *p = G.VerticesList[u].first; p != NULL; p = p-&gt;next)
        {
            int v = p-&gt;adjvex;
            if (!visited[v] &amp;&amp; dist[u] != INT_MAX &amp;&amp; dist[u] + p-&gt;weight &lt; dist[v])
            {
                dist[v] = dist[u] + p-&gt;weight;
                path[v] = u;
            }
        }
    }
    // 根据 dist 数组输出长度，根据 path 数组输出路径
}


<!-- page 148 -->

<!-- verified-by-hand -->
> [!success] 已结合原文第 148 页及 Markdown 上下文人工校对
> 这是分页后的 Dijkstra_AL 主体，选点后的逻辑被错嵌进扫描 j 循环并缺闭括号。
void Dijkstra_AL(ALGraph G, int start)
{
    int dist[MAXV], path[MAXV];
    bool visited[MAXV] = {false};
    for (int i = 0; i &lt; G.numVertices; i++) { dist[i] = INT_MAX; path[i] = -1; }
    dist[start] = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int u = -1, min_dist = INT_MAX;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (!visited[j] &amp;&amp; dist[j] &lt; min_dist) { min_dist = dist[j]; u = j; }
        if (u == -1) break;
        visited[u] = true;
        for (ArcNode *p = G.VerticesList[u].first; p; p = p-&gt;next)
        {
            int v = p-&gt;adjvex;
            if (!visited[v] &amp;&amp; dist[u] + p-&gt;weight &lt; dist[v])
            {
                dist[v] = dist[u] + p-&gt;weight;
                path[v] = u;
            }
        }
    }
}


对于邻接表来说，时间复杂度主要瓶颈在于选择距离最短的点，这一步可以使用优先队列优化（即堆），优化后的时间复杂度为 O(e+mlogm)。

<!-- page 149 -->

## 5.3.4 最小生成树

给定一个连通无向图G=(V， E)，其生成树是：

• 一个包含图中所有 n 个顶点、n-1 条边的无环子图。

• 每个顶点都能通过生成树中的边互相连通。

在所有可能的生成树中，边的权值之和最小的那一棵生成树，称为最小生成树。

## Prim算法

核心思想：从顶点的角度出发，初始时已选顶点集合只含起始顶点。每次将一个顶点纳入已选顶点集合，重复n-1次直到该集合包含所有顶点。 利

步骤:

1. 初始化。从源点出发，标记该顶点已选。

2. 重复执行 n-1 次：

a.每次从未选顶点中找出距离已选顶点集合最近的顶点k，将该顶点标记已选。

b. 更新未选中顶点到已选顶点集合的距离。


<!-- page 150 -->


## 邻接矩阵

伪代码如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 150 页及 Markdown 上下文人工校对
> 原代码会把邻接矩阵中的无边值 0 当作更小边更新，且输出语句损坏、缺少 parent。
void Prim(MGraph G)
{
    int cost[MAXV], parent[MAXV];
    bool visited[MAXV] = {false};
    int start = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        cost[i] = G.Edge[start][i] != 0 ? G.Edge[start][i] : INT_MAX;
        parent[i] = G.Edge[start][i] != 0 ? start : -1;
    }
    cost[start] = 0;
    visited[start] = true;
    for (int i = 1; i &lt; G.numVertices; i++)
    {
        int min = INT_MAX, k = -1;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (!visited[j] &amp;&amp; cost[j] &lt; min)
            {
                min = cost[j];
                k = j;
            }
        if (k == -1) break;
        visited[k] = true;
        // 输出边 &lt;parent[k], k&gt;
        for (int j = 0; j &lt; G.numVertices; j++)
            if (!visited[j] &amp;&amp; G.Edge[k][j] != 0 &amp;&amp; G.Edge[k][j] &lt; cost[j])
            {
                cost[j] = G.Edge[k][j];
                parent[j] = k;
            }
    }
}


<!-- page 151 -->