Dijkstra 是基于贪心的策略
简单最短路径问题：如果 i 到 j 的最短路经过 w，那么从 i 到 j 的最短距离一定为从 i 到 w 的最短距离加上从 w 到 j 的最短距离。
Dijkstra 不能处理带有负权边的情况
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 550;
int g[N][N]; // 用邻接矩阵存储图
int dist[N]; // 节点i到起点的最短距离
bool st[N]; // 判断节点i是否已经加入
int n, m;
int dijkstra()
{
// 初始化最短距离
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
// 已选节点个数从1~n
for(int i=1; i<=n; i++){
int t = -1;
// 节点从1到n开始遍历
for(int j=1; j<=n; j++){
// 选取还没加入 且 距离最短的节点
if(!st[j] && (t==-1 || dist[j]<dist[t])) {
t = j;
}
}
// 加入该节点
st[t] = true;
// 更新最短距离
for(int j=1; j<=n; j++){
dist[j] = min(dist[j], dist[t]+g[t][j]);
}
}
// int为4个字节
// 如果dist[n]为无穷，说明无起点到n的最短路径
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
// 因为图中可能存在重边和自环，且所有边权均为正值
// 该情况下，最短路径一定不存在正环，所以需要将g[i][i]置为正无穷
// 将邻接矩阵初始化为正无穷
memset(g, 0x3f, sizeof(g));
int x, y, z;
for(int i=1; i<=m; i++){
cin >> x >> y >> z;
// 不是正环的情况下，更新g
if(x != y) {
// 重边只选取最小的
g[x][y] = min(g[x][y], z);
}
}
int res = dijkstra();
cout << res << endl;
return 0;
}
dist[i]表示节点 i 到起点的最短距离。dist[i]=INF，dist[1]=0。dist[i]，然后吧节点 t 加入集合 s 中。#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 200000;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N]; // 记录边的权重
int dist[N]; // 到节点1的最短距离
bool st[N]; // 记录节点是否已加入集合
// 存在一条边，由a指向b，权重为c
void add(int a, int b, int c)
{
// 边idx指向节点b
e[idx] = b;
w[idx] = c;
// 边idx的下一条边是h[a]
ne[idx] = h[a];
// 节点a最新的一条边（表头）是idx
h[a] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f3f3f3f, sizeof(dist));
dist[1] = 0;
// first: 到节点1的距离
// second: 节点编号
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 将起始节点加入堆中
heap.push({0, 1});
while(heap.size() > 0) {
// 取出到节点1距离最短的点
auto t = heap.top();
heap.pop();
int d = t.first;
int v = t.second;
// 如果当前节点未加入集合
if(st[v] == false) {
st[v] = true;
// 更新最短节点
for(int i=h[v]; i!=-1; i=ne[i]) {
int j = e[i];
if(dist[j] > d+w[i]) {
dist[j] = d+w[i];
// 这里不更新堆中元素，直接插入堆
// 旧的一定比新的大，冗余后面会被pop出去
heap.push({dist[j], j});
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
// 初始化
cin >> n >> m;
memset(h, -1, sizeof(h));
for(int i=0; i<m; i++) {
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
cout << dijkstra() << endl;
return 0;
}
如果有负权边的话，最短路不一定存在
Bellman - ford 算法的核心思想是动态规划
状态定义：dist[i]表示经过 k 条边（该变量是隐含的），从源点到 i 的最短距离
状态计算：
dist[v] = min(dist[v], dist[u] + w[u, v])Bellman - ford 可以解决负环的问题
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 550, M = 10010;
// 定义边的数据类型
struct Edge
{
int a, b, c;
} edges[M];
int n, m, k;
int dist[N]; // 从源点到i的最短路径长度（隐含经过了k条边）
int last[N]; // 上一状态的最短路径，经过k-1条边的最短路径长度
void bellman()
{
// 初始化
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0; // 源点
// 经过i条边
for(int i = 1; i <= k; i++) {
// 数组拷贝
memcpy(last, dist, sizeof(dist));
// 松弛操作
for(int j = 0; j < m; j++) {
auto e = edges[j];
// 假设源点能到a，则源点到b的最短距离为min(dist[b], last[a]+c)
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
int main()
{
cin >> n >> m >> k;
for(int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
bellman();
if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
else cout << dist[n] << endl;
return 0;
}
spfa 本质上是对 bellman - ford 算法的一种队列优化
st数组标记节点是否发生了更新，避免重复入队。Dijkstra 算法 与 SPFA 算法的比较：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100100;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; // 记录当前发生过更新的点
bool st[N]; // 标记节点是否发生了更新，避免重复入队
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa()
{
// 初始化
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
// 记录当前发生过更新的点
queue<int> q;
// 判断与源点相邻的节点是否能更新
q.push(1);
st[1] = true;
while(q.size() > 0) {
int t = q.front();
q.pop();
// 相邻节点遍历，需要置回false
st[t] = false;
// 检查相邻节点是否能更新
for(int i = h[t]; i != -1; i = ne[i]) {
// 边：t-j
int j = e[i];
if(dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
// 如果节点 j 上一轮没更新过
if( !st[j] ) {
// 加入邻接节点待更新的队列
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
// 初始化
cin >> n >> m;
memset(h, -1, sizeof(h));
for(int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if(t == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
贫穷的小 A 有一个梦想，就是到 t 国去一次穷游，但现实是残酷的。小 A 所在的世界一共有 n（n<=500）个国家，国家与国家之间总共有 E（E<=50000）条道路相连，第 i 个国家对于进入它的外国人都要收取 Bi 的费用，而小 A 家住在 s 国，他必须通过这些道路在各个国家之间中转最终到达 t 国（除非他运气够好可以直接从 s 国到达 t 国）。但是贫穷的小 A 只剩下 M（M<=100）元家底了，因此他必须精打细算旅途的费用，同时小 A 对于 t 国实在太向往了，因此他希望能够走最短的路尽快到达t国。这个问题难倒了小 A，现在他请你帮他算一算他到达t国的最短路径有多长。
第一行输入T(T<=10)表示有T组数据。每组数据第一行输入n、E、s、t、M，分别表示小A所在世界的国家数、国家之间的总道路数、小A的国籍、小A向往的国家以及小A的家底；接下来一行输入n个正整数Bi，表示第i个国家收取的过路费（由于小A是s国人，因此s国不会收取，但t国会）；接下来输入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w，表示u国和v国之间存在着一条长度为w的无向边（可能有重边）。输入保证最终结果不会使int溢出。
输出T行正整数，第i行表示第i组数据小A花费不超过M元到达t国的最短路。若小A无法到达t国，输出-1.
这道题结合了 SPFA 求最短路和背包问题。
对于这道题，我们可以将最短路径看成背包装物品的价值，将小 A 的预算看成背包的容量。
状态定义：dist[i][j]表示从源节点出发，到达节点 i，预算为 j 的最短路径长度。
状态计算：
(a, b)，边(a, b)的路径长度为c，点b的过路费为cost[b]，则dist[i][j] = min(dist[i][j], dist[b][j - cost[b]] + c)#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
using namespace std;
int T;
int n, m, s, t, money;
const int N = 550, E = 100010, M = 110, INF = 0x3f3f3f3f;
int dist[N][M]; // dist[i][j]：从源节点到i，费用为j的最短路径
int cost[N]; // 过路费
int h[N], w[E], e[E], ne[E], idx;
bool st[N]; // 标记节点是否发生了更新
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa()
{
// 初始化
for(int i = 1; i <= n; i++) {
for(int j = 0; j <=money; j++) {
if(i == s) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
memset(st, false, sizeof(st));
queue<int> q;
// 需要判断与s相邻的节点是否能更新
q.push(s);
st[s] = true;
while( !q.empty() ) {
int top = q.front();
q.pop();
// 相邻节点遍历，需要置回false
st[top] = false;
// 检查相邻节点是否能更新
for(int i = h[top]; i != -1; i = ne[i]) {
// 边：top-j
int j = e[i];
for(int k = cost[j]; k <= money; k++) {
if(dist[j][k] > dist[top][k - cost[j]] + w[i]) {
dist[j][k] = dist[top][k - cost[j]] + w[i];
// 如果节点 j 上一轮没更新过
if( !st[j] ) {
// 加入邻接节点待更新的队列
q.push(j);
st[j] = true;
}
}
}
}
}
int res = INF;
for(int i = 0; i <= money; i++) {
res = min(res, dist[t][i]);
}
if(res == INF) res = -1;
return res;
}
int main()
{
cin >> T;
while( T-- ) {
cin >> n >> m >> s >> t >> money;
for(int i = 1; i <= n; i++) {
cin >> cost[i];
}
cost[s] = 0;
int a, b, c;
memset(h, -1, sizeof(h));
idx = 0;
for(int i = 0; i < m; i++) {
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
cout << spfa() << endl;
}
return 0;
}