最小生成树问题

Prim 算法

从某一个结点开始构建生成树，每次将代价最小的新结点纳入生成树，直到所有的结点都纳入为止。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (int k = 0; k < n - 1; k++) // 算法总共需要 n - 1 轮处理
{
    int min = 0;

    for (int i = 0; i < n; i++) // 循环遍历所有结点, 找到代价最小的新结点
    {
        if (!tag[i] && cost[i] < cost[min])
        {
            min = i;
        }
    }

    tag[min] = true;
    for (int i = 0; i < n; i++) // 循环遍历所有结点, 更新最小代价信息
    {
        if (!tag[i] && cost[i] > graph[min][i])
        {
            cost[i] = graph[min][i]; // 更新最小代价
        }
    }
}

Kruskal 算法

每次选择一条权值最小的边，使这条边的两头连通，直到所有的结点都连通为止。

总结

Prim 算法和 Kruskal 算法的核心思想都是贪心原则，但区别在于前者从顶点（结点）出发构建生成树，后者从边出发构建生成树。

最短路径问题

解决最短路径问题可以使用最基本的 BFS 算法，但它只适用于在无权图上，求单源最短路径的情况，这是远远不够的。

Dijkstra 算法

适用于在带正权图（包括无权图，即每条边的权值为 1）上，求单源最短路径。从某一个结点开始寻找到其他所有结点的最短路径，每次选择代价最小的新结点，并更新最短路径数组，直到所有可达的结点都选择完毕。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for (int k = 0; k < n - 1; k++) // 算法总共需要 n - 1 轮处理
{
    int min = 0;

    for (int i = 0; i < n; i++) // 循环遍历所有结点, 找到代价最小的新结点
    {
        if (!tag[i] && dist[i] < dist[min])
        {
            min = i;
        }
    }

    tag[min] = true;
    for (int i = 0; i < n; i++) // 循环遍历所有以代价最小结点为结点的边, 更新最短路径信息
    {
        if (!tag[i] && dist[i] > dist[min] + graph[min][i]) // 对于第 i 个结点, 如果以第 min 个结点为中转点的路径更短, 就进行一次「松弛」操作
        {
            dist[i] = graph[min][i]; // 更新最短路径长度
            path[i] = min;           // 记录中转点
        }
    }
}

总结

Prim 算法和 Dijkstra 算法虽然高度相似，但除了目的不同（前者用于构建最小生成树，后者用于求最短路径）、适用范围不同（前者适用于无向图，后者适用于有向图）之外，最大的区别在于前者更新的是已标记集合到未标记结点之间的距离，后者更新的是源点到未标记结点之间的距离，即所谓的「代价最小」说的不是一回事。

Bellman-Ford 算法

适用于在带权图（包括正权图、负全图和无权图）上，求单源最短路径。每次都考察图中所有的边，不断更新最短路径数组，直到最短路径数组不再更新为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int k = 0; k < n - 1; k++)  // 算法总共需要 n - 1 轮处理
{
    for (int i = 0; i < n; i++) // 循环遍历所有边, 更新最短路径信息
    {
        for (int j = 0; j < n; j++)
        {
            if (dist[i] != INF && dist[j] > dist[i] + graph[i][j])  // 对于第 j 个结点, 如果以第 i 个结点为中转点的路径更短, 就进行一次「松弛」操作
            {
                dist[j] = dist[i] + graph[i][j];  // 更新最短路径
                path[j] = i;  // 记录中转点
            }
        }
    }
}

Floyd - Warshall 算法

适用于在带权图（包括正权图、负全图和无权图）上，求多源最短路径，可以求出每一对顶点（结点）之间的最短路径。

算法描述

  1. 从第一个结点开始考察作为中转点的情况，寻找所有结点对之间的最短路径，每次新增一个可允许中转的结点，并更新最短路径矩阵，直到所有结点都被考察完毕。

  2. 设最短路径矩阵为 $\pmb{D}$，当前考察的中转点为 $k$，则 Floyd 算法的状态转移方程为

    但由于

    同理有

    因此可以忽略 $k$，状态转移方程变形为

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int k = 0; k < n; k++) // 考虑以第 k 个结点作为中转点
{
    for (int i = 0; i < n; i++) // 循环遍历, 更新最短路径信息
    {
        for (int j = 0; j < n; j++)
        {
            if (dist[i][j] > dist[i][k] + dist[j][k]) // 如果以第 k 个结点为中转点的路径更短
            {
                dist[i][j] = dist[i][k] + dist[j][k]; // 更新最短路径长度
                path[i][j] = k;                       // 记录中转点
            }
        }
    }
}