最短路

最短路

最短路问题是图论中的一个经典问题，目标是找到一个图中某个起点到其他所有点或某些特定点的最短路径。最短路径的定义通常是边权和（在加权图中），或者边的数量（在无权图中）。

/*
最短路

单源最短路

	边权都是正数
		朴素的Dijkstra算法
		堆优化的Dijkstra算法		

	边权存在负边
		Bellman_Ford O(n*m)
		SPFA 一般O(m)，最坏O(n*m)

多元汇最短路
	
	Floyd算法 O(n^3)
*/

Floyd算法

# include <iostream>
# include <climits>
/*
	得到图中任意两点的最短距离
	时间复杂度O(n^3)，空间复杂度O(n^2)
	适用于任何图，不管有向无向，不管边权正负，但不能有负环
*/
int n, m;
const int N = 111;
int distance[N][N];

void floyd(){
	// 有跳板时
	// i -> ....... bridge ..... -> j
	// distance[i][j]能不能缩短
	// distance[i][j] = min(distance[i][j], distance[i][bridge] + distance[bridge][j])
	// 三层循环：枚举中间节点、起始节点、终止节点
	for (int bridge = 1; bridge <= n; bridge++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (distance[i][bridge] != INT_MAX && distance[bridge][j] != INT_MAX &&
					distance[i][j] > distance[i][bridge] + distance[bridge][j]) {
					distance[i][j] = distance[i][bridge] + distance[bridge][j];
				}
			}
		}
	}
}

void solve() {
	std::cin >> n >> m;
	// 初始化
	// 对角线上为 0，其余为 INF
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) distance[i][j] = INT_MAX;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		// 如果有多条边，取最小的权值
		distance[u][v] = std::min(distance[u][v], w);
		distance[v][u] = std::min(distance[v][u], w);
	}
	floyd();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			std::cout << distance[i][j] << " ";
		}
		std::cout << '\n';
	}
}

signed main() {
	std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

dijkstra算法

#include <bits/stdc++.h>
#define int long long
using namespace std;

/*
	给定一个源点，求从源点到每个点的最短路径长度
	适用范围: 有向图，无向图，边的权值非负 
	时间复杂度: O(m * log m) 其中 m 为边数
	
	原理: 
	1. d[i]表示从源点到 i 点的最短距离，vis[i]表示 i 节点是否从小根堆弹出过
	2. 准备好小根堆，在里面存放{距离，节点}，小根堆根据距离组织
	3. 令 d[源点] = 0，将 {0，源点} 存入小根堆
	4. 从小根堆弹出(源点到 u 的距离，u点)
		a. 如果 vis[u] = true，不做任何处理，重复步骤4
		b. 如果 vis[u] = false，令 vis[u] = true，u 就算弹出过了
			然后考察 u 的每一条边，假设某条边去往 v, 并且边权为 w
			if (!vis[v] && d[u] + w < d[v]) {
			d[v] = d[u] + w;
			heap.push({d[v], v});
			}
			处理完 u 的每一条边之后, 重复步骤 4
	5. 小根堆为空过程结束，d表记录了源点到每个节点的最短距离
*/

vector<vector<pair<int, int>>> g;
vector<int> d;
vector<bool> vis;
int n, m, s;

void dijkstra(){	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
	// 距离在前，节点在后
	heap.push({0, s});
	while(!heap.empty()) {
		int u = heap.top().second;
		heap.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto edge : g[u]) {
			int v = edge.first;
			int w = edge.second;
			if (!vis[v] && d[u] + w < d[v]) {
				d[v] = d[u] + w;
				heap.push({d[v], v});
			}
		}
	}
}

void solve() {
	cin >> n >> m >> s;
	// 初始化
	d.assign(n + 1, INT_MAX);
	d[s] = 0;
	vis.assign(n + 1, false);
	g.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
	}
	dijkstra();
	for (int i = 1; i <= n; i++) cout << d[i] << " ";
	cout << endl;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

A*算法

// A*算法

// 源点 -> 目标点
// 其余部分和dijkstra算法一样
// 唯一的区别在于小根堆里面的排序
// 每次都是该点离源点的真实距离加上该点到目标点的预估距离
// 通过这种预估处理，可能会使更靠近目标点的点优先处理
// 从而提高效率

// 预估函数要保证x到终点的预估距离 <= x到终点的真实距离

// 对于01迷宫，只能上下左右移动，那么预估可以采用曼哈顿距离
// abs(x1 - x2) + abs(y1 - y2)
// 对于01迷宫，可以走斜线，预估的时候采用对角线距离
// max(abs(x1 - x2), abs(y1 - y2))

// dijkstra: d[x] + 0
// A*: d[x] + f(x)

Bellman_Ford算法

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
//#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;

// 每一轮考察每条边，每条边都尝试进行松弛操作，那么若干点的 d 会变小
// 当某一轮不在有松弛操作出现的时候，算法停止
// 时间复杂度O(n * m)
// 松弛的轮数 <= n - 1

// 从某个点出发会不会遇到负环
// 如果从 A 点出发发现在第 n 轮松弛操作依旧存在，说明 A 点出发可以到达一个负环

// 解决有边数限制的最短路

int n, m, k;

struct Edge{
	int u, v, w;
};

vector<Edge> g;
vector<int> d;
vector<int> last;

void bellman_ford(){
	d.assign(n + 1, INF);
	d[1] = 0;
	// 经过至少 k 条边的最短距离
	for (int i = 0; i < k; i++) {
		// 用 last 记录上一次的 d
		// 通过 last，保证了每一轮松弛操作只依赖于上一轮的最短路径，而不会受当前轮松弛操作的影响
		last = d;
		for (int j = 0; j < m; j++) {
			int u = g[j].u, v = g[j].v, w = g[j].w;
			if (d[v] > last[u] + w) {
				d[v] = last[u] + w;
			}
		}
	}
	if (d[n] > INF / 2) {
		cout << "impossible" << endl;
	} else {
		cout << d[n] << endl;
	}
}

void solve() {
	cin >> n >> m >> k;
	g.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> g[i].u >> g[i].v >> g[i].w;		
	}
	bellman_ford();
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

寻找负环

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int n, m, e;  
const int N = 1e5;  
struct Node {
    int u, v, w;
};
vector<Node> g(N);  
vector<int> d(N, INT_MAX);  

bool bellman_ford() {
    d[1] = 0;  
    // 每次松弛，能找到从起点出发经过 k 条边的最短距离
    for (int k = 1; k <= n - 1; k++) {
        for (int i = 0; i < e; i++) { 
            int u = g[i].u, v = g[i].v, w = g[i].w;
			// != INT_MAX 代表源点可以到达这个点
            if (d[u] != INT_MAX && d[u] + w < d[v]) {
                d[v] = d[u] + w;
            }
        }
    }
    // 如果还可以进行松弛操作
    for (int i = 0; i < e; i++) {
        int u = g[i].u, v = g[i].v, w = g[i].w;
        if (d[u] != INT_MAX && d[u] + w < d[v]) {
            return true;  
        }
    }
    return false;  
}

void solve() {
    cin >> n >> m; 
    // 注意全局变量的使用！
    e = 0; 
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 注意读题！
        if (w >= 0) {
            g[e++] = {u, v, w};
            g[e++] = {v, u, w};
        } else {
            g[e++] = {u, v, w};
        }
    }
    if (bellman_ford()) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;  
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;  
    while (T--) solve();  
    return 0;
}