学不会的图论——最短路篇
前言
因为camp第一天就讲了Dijkstra，就想着刚好把最短路都整了吧！
Floyd - Warshall
Floyd主要用来处理多源最短路问题，能够求出图中任意起点到任意终点的最短路径。适用于任何图，但是最短路必须存在（不能存在负环）。但是由于空间和时间的限制，在算法竞赛中，Floyd只能处理规模小的图。
算法思想
1、我们先定义一个邻接矩阵f[ ][ ]用来存图，f[i][j]表示，i到j的最短距离。初始化为无穷大，表示两点之间不能直接到达.
2、根据给出的数据进行存图
3、遍历图中任意两点，尝试在两点之间通过其他点中转。举个例子，不妨设i -> j，我们尝试通过k进行中转，即i -> k -> j，将两种路径中的最小值存入f[i][j]。
用代码表示上述过程为：
for (k = 1; k <= n; k ++) {
for (i = 1; i <= n; i ++) {
for (j = 1; j <= n; j ++) {
f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
}
}
}
判断负环
如果图中有权值为负的边，而且存在经过这条负边的环路，环路的所有边权加起来的总长度也是负的，我们就称这样的环为负环。
显然的，我们每在这个环上跑一圈，总长度就会减小，会陷入一直在负环上绕圈的死循环。
Floyd算法很容易判断负环，只要在算法运行过程中，出现任意的f[i][i] < 0，就说明有负环，因为f[i][i]是从i出发，经过其他中转点绕一圈回到自己的最短路径，如果小于0，就存在负环。
Minimum Transport Cost
Problem Description
These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts:
The cost of the transportation on the path between these cities, and
a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities.
You must write a program to find the route which has the minimum cost.
Input
First is N, number of cities. N = 0 indicates the end of input.
The data of path cost, city tax, source and destination cities are given in the input, which is of the form:
a11 a12 ... a1N
a21 a22 ... a2N
...............
aN1 aN2 ... aNN
b1 b2 ... bN
c d
e f
...
g h
where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form:
Output
From c to d :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......
From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......
Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.
Sample Input
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0
Sample Output
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
我的代码
#include<bits/stdc++.h>
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
int n;
int path[505][505];
int f[505][505];
int tax[505];
void init(){
for(int i = 0 ; i < 300 ; i ++){
for(int j = 0 ; j < 300 ; j ++){
f[i][j] = 0;
path[i][j] = 0;
}
}
}
void Floyd(){
for(int k = 1 ; k <= n ; k ++){
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= n ; j ++){
int t = f[i][k] + f[k][j] + tax[k];
if(f[i][j] > t){
f[i][j] = t;
path[i][j] = path[i][k];
}else if(f[i][j] == t && path[i][j] > path[i][k]){
path[i][j] = path[i][k];
}
}
}
}
}
void print(int i , int j){//输出路径
while (i != j){
std::cout << "-->" << path[i][j];
i = path[i][j];
}
std::cout << "\n";
}
void solve(){
while (std::cin >> n) {
if (n == 0) break;
init();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
std::cin >> f[i][j];
if (f[i][j] == -1) f[i][j] = INF;
path[i][j] = j;
}
}
for(int i = 1 ; i <= n; i ++) std::cin >> tax[i];
Floyd();
int x, y;
while (std::cin >> x >> y) {
if (x == -1 && y == -1) break;
std::cout << "From " << x << " to " << y << " :" << '\n';
std::cout << "Path: " << x ;
print(x,y);
std::cout << "Total cost : " << f[x][y] << "\n";
std::cout << "\n";
}
}
}
signed main() {
std::ios ::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t --){
solve();
}
return 0;
}
题目分析
很明显这题是Floyd的简单应用，唯一的难点是需要输出路径，并且在长度相等的情况下，选择字典序小的路径。
我们不妨设一个path[ ][ ]，记录i -> j的路径上出现的第一个点。显然，我们应将所有的path初始化为path[i][j] = j，若我们通过k中转，则更新为path[i][j] = path[i][k];
最后我们只需要不断地取path[i][j]，更新i = path[i][j]，直到i == j，说明我们已经遍历了i -> j的最短路
Dijkstra
Dijkstra主要用于处理“单源”最短路的问题，需要注意的是，不能存在负边权。我们可以将Dijkstra简单概括为“Dijkstra = BFS + 贪心”。
Q：为什么不能存在负边权？
A：就像刚刚提到的，因为Dijkstra算法基于BFS，计算过程是从起点开始向外扩散的过程，这时候我们保证：已经处理过的点的距离不会再发生变化。如果存在负边权的话，我们已经处理过的点就可能再次发生变化，使一些处理变得无效。
算法步骤
1、从起点0出发，用BFS扩展它相邻的节点1，2，把它们放到set（或者priority_queue）q中，并且记录0 -> 1 和 0 -> 2的距离。
2、选择到0最近的节点1，继续用BFS扩展1的相邻节点3，将3放入q。如果0 -> 3 > 0 -> 1 -> 3，则更新0 -> 3。
3、将1从q中移走，不再处理
4、重复上面的步骤，直到处理完全部的节点。
【模板】单源最短路径（标准版）
题目背景
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
\(100 \rightarrow 60\)；
\(\text{Ag} \rightarrow \text{Cu}\)；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 \(n\) 个点，\(m\) 条有向边的带非负权图，请你计算从 \(s\) 出发，到每个点的距离。
数据保证你能从 \(s\) 出发到任意点。
输入格式
第一行为三个正整数 \(n, m, s\)。
第二行起 \(m\) 行，每行三个非负整数 \(u_i, v_i, w_i\)，表示从 \(u_i\) 到 \(v_i\) 有一条权值为 \(w_i\) 的有向边。
输出格式
输出一行 \(n\) 个空格分隔的非负整数，表示 \(s\) 到每个点的距离。
样例 #1
样例输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
样例输出 #1
0 2 4 3
提示
我的代码
#include <bits/stdc++.h>
#define int long long
const int INF = 2147483647;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
struct edge{//存边
int to;
int w;
edge(int a,int b){
to = a;
w = b;
}
};
std::vector<edge> G[N];
int dis[N];
bool book[N];
struct node{
int id;
int dis;
node(int a,int b){
id = a;
dis = b;
}
bool operator < (const node &u) const{
return dis > u.dis;
}
};
void dijkstra(int s){
for(int i = 0;i < N;i ++){//初始化
dis[i] = INF;
book[i] = false;
}
dis[s] = 0;//自己到自己的距离为0
std::priority_queue<node> q;
q.push(node(s,dis[s]));
while (!q.empty()){
node u = q.top();
q.pop();
if(book[u.id]) continue;//如果这个点已经处理过，不需要再处理
book[u.id] = true;
for(auto i:G[u.id]){//遍历当前节点的所有相邻节点
if(book[i.to]) continue;//如果这个点已经处理过（起点方向的节点也是相邻节点）
if(dis[i.to] > dis[u.id] + i.w){
dis[i.to] = dis[u.id] + i.w;
q.push(node(i.to,dis[i.to]));//把当前点的相邻未处理节点加入q
}
}
}
}
void solve(){
int n,m,s;
std::cin >> n >> m >> s;
while (m --){
int u,v,w;
std::cin >> u >> v >> w;
G[a].push_back({b,w});
// G[b].push_back({a,w});//无向边存反图
}
dijkstra(s);
for(int i = 1;i <= n;i ++){
std::cout << dis[i] << " ";
}
std::cout << "\n";
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t --){
solve();
}
return 0;
}
Bellman-Ford
Bellman-Ford算法是处理单源最短路。跟Dijkstra相比，它能处理负边权，同样需要判断负环，但是，它同Floyd一样只能处理小图，但比Floyd要好。
算法的执行过程
1、从起点s开始，与s直接相连的点肯定有一点u是最近的，第一轮能够确定s到u的最短路径。需要注意的是，我们不需要记录此时的u是哪个点，因为经过n轮后所有的点到s的最短路径都能被确定。
2、再次，查询所有点直接相连的点，是否有到s的更短路；类似于Floyd插点的操作，这个点要么与s直接相连，要么与u直接相连
3、重复以上步骤，每轮能确定一个点的最短路径。n个点共进行n轮计算，每轮需要检查m条边，总复杂度为O(mn)；
最短路
Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
我的代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e4 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n , m;
int cnt = 1;
struct EDGE {
int u;
int v;
int w;
EDGE(int a, int b, int c) {
u = a;
v = b;
w = c;
}
EDGE(){
}
}edge[N];
void Bellman(){
int s = 1;
int d[N];
for(int i = 1 ; i <= n ; i ++){
d[i] = INF;
}
int min = d[s];
d[s] = 0;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1; j < cnt ; j ++){
int x = edge[j].u;
int y = edge[j].v;
if(d[x] > d[y] + edge[j].w){
d[x] = d[y] + edge[j].w;
}
}
}
std::cout << d[n] << "\n";
}
void solve(){
while (std::cin >> n >> m){
if(n == 0 && m == 0) break;
cnt = 1;
for(int i = 1 ; i <= m ; i ++){
int a , b , c;
std::cin >> a >> b >> c;
edge[cnt ++] = {a,b,c};
edge[cnt ++] = {b,a,c};
}
Bellman();
}
}
signed main() {
std::ios ::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t --){
solve();
}
return 0;
}
SPFA
SPFA(Shortest Path Faster Algorithm)，简单来说就是用队列优化的Bellman-Ford算法，每一轮计算只需要更新上一轮有变化的那些点，我们不妨将变化了的点压入队列中用于下次处理。SPFA在一般情况下和Dijkstra一样好，甚至可能更好，但是最坏的情况下，复杂度仍为O(mn);
执行步骤
1、起点s入队，s出队，遍历s直接相连的点，有更新的点入队。
2、现在队列的top是一个与s直接相连的点u。弹出u，遍历u直接相连的点，有更新的点入队。
3、持续上述过程直到队列为空。意味着所有节点都不再更新，最后的状态就是到起点s的最短路
上面那个题目的SPFA写法
#include<bits/stdc++.h>
#define int long long
const int N = 1e4 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n , m;
int dis[N];
bool vis[N];
int negativeLoop[N];
int pre[N];
struct edge{
int v , w;
};
std::vector<edge> edge[N];
int SPFA(int s){
std::memset(negativeLoop , 0 , sizeof(negativeLoop));
for(int i = 1 ; i <= n ; i ++) dis[i] = INF;
std::memset(vis , 0 , sizeof(vis));
std::queue<int> q;
q.push(s);//起点入队
vis[s] = true;
dis[s] = 0;
while (!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(auto v : edge[u]){
if(dis[u] + v.w < dis[v.v]){//如果v.v通过u到达起点的路径更小更新
dis[v.v] = dis[u] + v.w;
pre[v.v] = u;
if(!vis[v.v]){//v.v这个点的状态更新了，但是v.v这个点不在队列中
vis[v.v] = true;
negativeLoop[v.v] ++;//某个点出现的次数
if(negativeLoop[v.v] > n) return 1;//在n个点的图中（不存在重边）一个点最多被连接n次，超过n次，说明存在负环
q.push(v.v);
}
}
}
}
return 0;
}
void print(int i , int j){//输出路径
if(i == j) {
std::cout << i;
return ;
}
print(i , pre[j]);
std::cout << " " << j;
}
void solve() {
while (std::cin >> n >> m) {
if(n == 0 && m == 0) break;
for(int i = 1 ; i <= n ; i ++) edge[i].clear();
for (int i = 1; i <= m; i++) {
int x, y, w;
std::cin >> x >> y >> w;
edge[x].push_back({y , w});//无向图存图
edge[y].push_back({x , w});
}
SPFA(1);
std::cout << dis[n] << "\n";
// print(1,n);
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0); std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}