最短路

2021 年 1 月 30 日 星期六(已编辑)
1
这篇文章上次修改于 2021 年 1 月 30 日 星期六，可能部分内容已经不适用，如有疑问可询问作者。

最短路

最短路

定义

最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。

——百度百科

名词解释

  • Chain · 链：一个点和边的交错序列 v0−e1−v1−e2−v2−⋯−ek−vkv_0 - e_1 - v_1 - e_2 - v_2 - \cdots - e_k - v_k
  • Trail · 迹：对于一条路径 ww，若e1,e2,⋯ ,eke_1, e_2, \cdots, e_k 两两互不相同，则 ww 是一条迹
  • Path · 路径：对于一条迹 ww，除了 v0v_0 和 vkv_k 允许相同外，其余点两两互不相同，则称 ww 是一条路径
  • Circuit · 回路：对于一个迹 ww，若 v0=vkv_0 = v_k，则称 ww 是一个回路
  • Cycle · 环：对于一条路径 ww，若 v0=vkv_0 = v_k，则称 ww 是一个环

分类

  • 单源最短路

    包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 。

  • 多源最短路

链式前向星

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f

int n, m;    //n 个点，m 条单向边
int cnt;
int front[10001];

struct EDGE
{
    int to, next, w;
};

EDGE edge[10001];

void Init()
{
    memset(front, 0, sizeof(front));
    cnt = 0;
}

void add_edge(int u, int v, int w)
{
    ++cnt;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = front[u];
    front[u] = cnt;
}

int main()
{
    freopen("in.txt", "r", stdin);
    Init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);    //双向边
    }

    //遍历与每个点相连的所有边
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", i);
        for (int j = front[i]; j; j = edge[j].next)
        {
            printf("%d %d %d\n", i, edge[j].to, edge[j].w);
        }
        printf("\n");
    }

    return 0;

}

Dijkstra · 单源最短路

思路

  1. 将所有节点分成两个集合，已求出最短路的集合（集合1）和未求出最短路的集合（集合2）。
  2. 更新并记录集合2 中所有节点和源点的距离
  3. 从集合2 中找到距离源点距离最近的点
  4. 将该点移到集合1 中
  5. 重复步骤 2-3，直到集合2 为空

这个方法用了贪心的思想，每次把距离最小的点视作确定的，因为它已经是未确定的点中距离源点最近的了，不可能存在一条路经过其他未确定的点到这个点，距离还比直接到这个点近的了。

  • 不能有负权边

模板

  • dis[]：每个点到源点的距离
  • vis[]：每个点属于的集合，0 - 未确定，1 - 已确定
#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f

int n, m;    //n 个点，m 条边
int mp[10001][10001];
int dis[10001], vis[10001];

void Init()
{
    memset(mp, INF, sizeof(mp));
    for (int i = 1; i <= n; i++) mp[i][i] = 0;
}

void Getmap()
{
    int u, v, w;
    for (int t = 1; t <= m; t++)
    {
        scanf("%d%d%d", &u, &v, &w);
        if (w < mp[u][v])
        {
            mp[u][v] = w;
            mp[v][u] = w;
        }
    }
}

void Dijkstra(int x)
{
    memset(vis, 0, sizeof(vis));
    for (int t = 1; t <= n; t++) dis[t] = mp[x][t];

    vis[x] = 1;
    for (int t = 1; t < n; t++)
    {
        int minn = INF, temp;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[i] < minn)
            {
                minn = dis[i];
                temp = i;
            }
        }
        vis[temp] = 1;
        for (int i = 1; i <= n; i++)
            if (mp[temp][i] + dis[temp] < dis[i])
                dis[i] = mp[temp][i] + dis[temp];
    }
}

int main()
{
    scanf("%d%d", &n, &m);    //n 个点，m 条边
    Init();    //地图初始化
    Getmap();    //读图
    Dijkstra(x);    //以点 x 为出发点的单源最短路
    for (int i = 1; i <= n; i++) printf("%d\t%d\n", i, dis[i]);    //dis[i]：x 点到 n 点的最短距离


    return 0;

}

复杂度 · O(n<sup>2</sup>)O(n<sup>2</sup>)

拓展

  • 从一个点出发到所有点的距离：正 Dijkstra

  • 从所有点出发到一个点的距离（POJ 3268 · Silver Cow Party）

    • 把图反向

      int tmp = map[i][j];
map[i][j] = map[j][i];
map[j][i] = tmp;

    • Dijkstra

优化

Floyd · 多源最短路

思路

我们定义一个数组 dis[k][x][y] ，表示只允许经过结点 V1V_1 到 VkV_k，结点 xx 到结点 yy 的最短路长度。很显然， dis[n][x][y] 就是最终结点 xx 到结点 yy 的最短路长度。

dis[0][x][y] 是 xx 与 yy 的边权，或者 00，或者 ∞\infty（当 xx 与 yy 间有直接相连的边的时候，为它们的边权；当 x=yx = y 的时候为零，因为到本身的距离为零；当 xx 与 yy 没有直接相连的边的时候，为 ∞\infty）

dis[k][x][y] = min(dis[k-1][x][y], dis[k-1][x][k]+dis[k-1][k][y]) （ dis[k-1][x][y] 为不经过 kk 点的最短路径，而 dis[k-1][x][k]+dis[k-1][k][y] 为经过了 kk 点的最短路）。

  • 能有负权边

  • 不能有负环

模板

void Floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dis[k][i][j] = min(dis[k - 1][i][j], dis[k - 1][i][k] + dis[k - 1][k][j]);
            }
        }
    }
}

不难看出，kk 每次循环后只是调用了 k−1k - 1 的数据，而 kk 之前的数据对结果没有作用，因此第一维是可以省略的（数据可以不保存，直接在下一次循环被覆盖，但是还是需要有这 kk 次循环）

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f

int n, m;    //n 个点，m 条边
int dis[10001][10001];

void Init()
{
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
}

void Getmap()
{
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (w < dis[u][v])
        {
            dis[u][v] = w;
            dis[v][u] = w;
        }
    }
}

void Floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    Init();
    Getmap();
    Floyd();
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            printf("%d %d %d\n", i, j, dis[i][j]);  //dis[i][j] = i 到 j 的最短距离
        }
    }


    return 0;

}

复杂度

  • 时间复杂度：O(n3)O(n^3)
  • 空间复杂度：O(n2)O(n2)

Bellman-Ford · 单源最短路

思路

  • 松弛

    每次松弛操作实际上是对相邻节点的访问，第 nn 次松弛操作保证了所有深度为 nn 的路径最短。由于图的最短路径最长不会经过超过 ∣V∣−1|V| - 1 条边，所以可知贝尔曼-福特算法所得为最短路径。

  • 负边权操作

    与 Dijkstra 算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

  • 负权环判定

    因为负权环可以无限制的降低总花费，所以如果发现第 nn 次操作仍可降低花销，就一定存在负权环。

  • 能有负权边

  • 能有负环

优化

  • 循环的提前跳出

    在实际操作中，贝尔曼-福特算法经常会在未达到 ∣V∣−1|V| - 1 次前就出解，∣V∣−1|V| - 1 其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

  • 最短路径快速算法

    松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。该算法的复杂度为 O(k∣E∣)O(k|E|)，kk 是个比较小的系数，但该结论未得到广泛认可。

模板

  • SPFA已死
#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f

int n, m;    //n 个点，m 条单向边
int cnt;
int dis[10001];
int front[10001];

struct EDGE
{
    int to, next, w;
};

EDGE edge[10001];

void Init()
{
    memset(front, 0, sizeof(front));
    cnt = 0;
}

void add_edge(int u, int v, int w)
{
    ++cnt;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = front[u];
    front[u] = cnt;
}

bool SPFA(int s)
{
    queue<int> q;
    bool vis[10001];
    int  cnt[10001];
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    while (!q.empty()) q.pop();
    dis[s] = 0;
    cnt[s] = 1;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = front[x]; i; i = edge[i].next)
        {
            int k = edge[i].to;
            if (dis[k] > dis[x] + edge[i].w)
            {
                dis[k] = dis[x] + edge[i].w;
                cnt[k] = cnt[x] + 1;
                if (cnt[k] > n) return 0;
                if (!vis[k])
                {
                    vis[k] = 1;
                    q.push(k);
                }
            }
        }
    }
    return 1;
}

int main()
{
    freopen("in.txt", "r", stdin);
    Init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);    //双向边
    }

    //SPFA(x)：以 x 点为源点的单源最短路
    //dis[y]：x 到 y 的最短距离
    //SPFA 返回值：是否存在负环
    for (int i = 1; i <= n; i++)
    {
        if (!SPFA(i)) printf("%d Yes\n", i);
        else printf("%d No\n", i);
        for (int j = 1; j <= n; j++)
        {
            printf("%d %d %d\n", i, j, dis[j]);
        }
        printf("\n");
    }

    return 0;

}

复杂度 · O(∣V∣⋅∣E∣)O(|V| · |E|)

习题

A 最短路 · HDU 2544

B Til the Cows Come Home · POJ 2387

C Silver Cow Party · POJ 3268

D Heavy Transportation · POJ 1797

E Cow Contest · POJ 3660

F Edge Deletion · CodeForces 1076D

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...