最短路

定义

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

——百度百科

名词解释

• Chain · 链：一个点和边的交错序列 $v_0 - e_1 - v_1 - e_2 - v_2 - \cdots - e_k - v_k$
• Trail · 迹：对于一条路径 $w$，若$e_1, e_2, \cdots, e_k$ 两两互不相同，则 $w$ 是一条迹
• Path · 路径：对于一条迹 $w$，除了 $v_0$ 和 $v_k$ 允许相同外，其余点两两互不相同，则称 $w$ 是一条路径
• Circuit · 回路：对于一个迹 $w$，若 $v_0 = v_k$，则称 $w$ 是一个回路
• Cycle · 环：对于一条路径 $w$，若 $v_0 = v_k$，则称 $w$ 是一个环

分类

• 单源最短路

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

• 多源最短路

链式前向星

#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²)$

拓展

• 从一个点出发到所有点的距离：正 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] ，表示只允许经过结点 $V_1$ 到 $V_k$，结点 $x$ 到结点 $y$ 的最短路长度。很显然， dis[n][x][y] 就是最终结点 $x$ 到结点 $y$ 的最短路长度。

dis[0][x][y] 是 $x$ 与 $y$ 的边权，或者 $0$，或者 $\infty$（当 $x$ 与 $y$ 间有直接相连的边的时候，为它们的边权；当 $x = y$ 的时候为零，因为到本身的距离为零；当 $x$ 与 $y$ 没有直接相连的边的时候，为 $\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] 为不经过 $k$ 点的最短路径，而 dis[k-1][x][k]+dis[k-1][k][y] 为经过了 $k$ 点的最短路）。

• 能有负权边

• 不能有负环

模板

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]);
            }
        }
    }
}

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

#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(n^3)$
• 空间复杂度：$O(n2)$

Bellman-Ford · 单源最短路

思路

• 松弛

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

• 负边权操作

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

• 负权环判定

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

• 能有负权边

• 能有负环

优化

• 循环的提前跳出

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

• 最短路径快速算法

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

模板

• 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|)$

习题

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