标签：const idx int 短路 汇总 更新 st 问题
-
最短路
-
单源最短路
- 求从一个点到其他所有点的最短距离
-
所有边权是正数
- 朴素Dijkstra算法 O(n^2)
- 用于稠密图 m >= n
- 步骤：
- dist[i]：每个点离起点的距离
- S：已经确定最短距离的点
- V：没有确定最短距离的点
- 初始化所有点的距离dist[起点] = 0；dist[其他点] = inf
- 循环找V中离起点最近的点t
- 将t放入S中
- 用t的距离更新其他点的距离
- 代码：
const int N = 510;
int g[N][N];//稠密图用邻接矩阵
int dist[N];//到原点的距离
int st[N];//标记数组
int dijkstra(){
//初始化距离
memset(d, 0x3f, sizeof d);
d[1] = 0;
//遍历n次每次找距离原点最近的节点
for(int i = 1; i <= n; ++ i){
//在n个接节点中找
int t = 0;
for(int j = 1; j <= n; ++ j)
if(!st[j] && (!t || d[t] > d[j])
t = j; //找到了
}
st[t] = 1; //标记已经找到最短距离
//更新所有节点的距离
for(int j = 1; j <= n; ++ j)
d[j] = min(d[j], d[t] + g[t][j]);
if(d[n] == 0x3f3f3f3f) return -1;//1-n不连通
else return d[n]; //返回1-n的最短距离
}
//注意初始化边权为inf
memset(g, 0x3f, sizeof g);
//输入边权
while(m -- ){
int a, b, c;
cin >> a >> b >> c;
//有重边就取最小边权
g[a][b] = min(g[a][b], c);
- 堆优化Dijkstra算法 O(mlogn)
- 用于稀疏图 m <= n
- 用堆存储每个节点的距离，堆顶元素就是离原点距离最近的节点
- 代码：
const int N = 1.5e5 + 10;
typedef pair<int, int> PII;
int st[N];
int h[N], e[N], ne[N], idx = 1;
int d[N], w[N];//w[i]边i的权值
int n, m;
void add(int x, int y, int z){
e[idx] = y;
ne[idx] = h[x];
h[x] = idx;
w[idx] = z;
idx ++ ;
}
int dijkstra(){
//初始化
memset(d, 0x3f, sizeof d);
d[1] = 0;
priority_queue<PII, vector<PII>, greater<PII> > q;//小根堆
q.push({0, 1});//起点入堆
while(q.size()){
auto t = q.top();//取堆顶元素，离起点最近的节点
q.pop();
int dist = t.first, node = t.second;//获取信息
if(st[node]) continue;//已经求出最短距离就跳过
st[node] = 1;
for(int i = h[node]; i; i = ne[i]){
int j = e[i];//遍历相连的所有节点
if(d[j] > dist + w[i]){//更新最短距离
d[j] = dist + w[i];
q.push({d[j], j});//入堆
}
}
}
if(d[n] == 0x3f3f3f3f) return -1;
else return d[n];
}
-
存在边权是负数
- Bellman-Ford算法 O(nm)
- 能够找到有边数限制的最短路径
- 可以判断图中有无负权回路
- 当外层循环执行n次（最短路更新了n次），说明最大有n条边构成了最短路，即有n+1个节点构成了最短路，根据鸽巢原理知，路中必有两个相同的节点，即路中有回路，又最短路更新的前提是最短路可以变得更小，所以该回路一定构成负权回路
- 当有边数限制时，即使图中有负环也无所谓，因为负环不能被无限选择
- 代码：
const int N = 510;
const int M = 1e4 + 10;
struct egde{ //边
int u, v, w;
}edges[M];
int d[N], backup[N];//备份数组
int n, m, k;
int ballmen_ford(){
//初始化
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 1; i <= k; ++ i){ //k条边限制
memcpy(backup, d, sizeof d); //存备份
for(int j = 1; j <= m; ++ j){ //遍历每一条边
int u = edges[j].u; //获取信息
int v = edges[j].v;
int w = edges[j].w;
d[v] = min(d[v], backup[u] + w); //利用备份更新
}
}
if(d[n] > 0x3f3f3f3f / 2) return -N;
else return d[n];
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= m; ++ i){
int x, y, z;
cin >> x >> y >> z;
edges[i] = {x, y, z};
}
int t = ballmen_ford();
if(t == -N) cout << "impossible";
else cout << t << endl;
return 0;
}
- SPFA算法 一般O(m)最坏O(nm)
- 相当于优化版的ballmen_ford
- 可以用于判断图中是否有负权回路
- 设置cnt[i]数组，表示最短路从起点到i的边的数量，当某时刻边的数量>=n，说明路中有回路
- 代码：
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx = 1;
int d[N], w[N], cnt[N];//cnt[i]数组表示从起点到i的最短路中的边的数量
int st[N]; //标记元素是否已经进入队列
int n, m;
void add(int a, int b, int z){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
w[idx] = z;
idx ++ ;
}
bool spfa(){
queue<int> q;
for(int i = 1; i <= n; ++ i){//所有节点入队，负环有可能不是从1-n路径上的，所以以每个节点为起点的路径都要检查
q.push(i);
st[i] = 1;//标记已入队
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = 0;//出队
for(int i = h[t]; i; i = ne[i]){
int j = e[i];
if(d[j] > d[t] + w[i]){
d[j] = d[t] + w[i]; //更新
cnt[j] = cnt[t] + 1;//边数加一
if(cnt[j] >= n) return true;//边数>=n时，说明有环
if(!st[j]){
q.push(j);//只将更新过的元素入队
st[j] = 1;
}
}
}
}
return false;
}
int main(){
cin >> n >> m;
while(m -- ){
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
if(spfa()) cout << "Yes";
else cout << "No";
return 0;
}
- d[v] = min(d[v], backup[u] + w); //利用备份更新，这句话存在很多无效更新。只有当u更新过后，d[v]的更新才有效，因此只需要将更新过的节点放入一个集合，每次只用在集合中取元素去更新它邻接的节点
- 有些正权图也可以用SPFA算法
- 代码：
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx = 1;
int d[N], w[N];
int st[N]; //标记元素是否已经进入队列
int n, m;
void add(int a, int b, int z){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
w[idx] = z;
idx ++ ;
}
int spfa(){
//初始化
memset(d, 0x3f, sizeof d);
d[1] = 0;
//队列存储更新过距离的节点
queue<int> q;
q.push(1);
st[1] = 1;//标记已入队
while(q.size()){//循环
int t = q.front();
q.pop();
st[t] = 0;
for(int i = h[t]; i; i = ne[i]){
int j = e[i];
if(d[j] > d[t] + w[i]){
d[j] = d[t] + w[i]; //更新
if(!st[j]){
q.push(j);//只将更新过的元素入队
st[j] = 1;
}
}
}
}
if(d[n] > 0x3f3f3f3f / 2) return -N;
else return d[n];
}
int main(){
cin >> n >> m;
while(m -- ){
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
int t = spfa();
if(t == -N) cout << "impossible";
else cout << t;
return 0;
}
- 存在负权边的图中存在最短路的话，图中一定不能有负权回路，除非最短路边数有限制，否则一直沿着回路绕，路径越来越小，直到最短路为负无穷
-
多源汇最短路
- 源点起点，汇点终点，起点与终点任意选取
- Floyd算法 O(n^3)
- 可以处理有负权的图，但不能处理有负权回路的图
- 代码：
const int N = 210;
const int M = 2e4 + 10;
const int INF = 0x3f3f3f3f;
int d[N][N];//存储两点间的最短路
int n, m, k;
void floyd(){
//基于动态规划
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
cin >> n >> m >> k;
//初始化
for(int i = 1; i <= n; ++ i)
for(int j = 1;j <= n; ++ j)
if(i == j) d[i][j] = 0; //去自环
else d[i][j] = INF;
while(m -- ){
int x, y, z;
cin >> x >> y >> z;
d[x][y] = min(d[x][y], z);//去重边
}
floyd();
while(k -- ){
int u, v;
cin >> u >> v;
int t = d[u][v];
if(t > INF / 2) cout << "impossible" << endl;
else cout << t << endl;
}
return 0;
}
标签：const,
idx,
int,
短路,
汇总,
更新,
st,
问题
From： https://www.cnblogs.com/moilip/p/17606826.html