最短路

Fri Oct 04 2024

zzcoe

10 分钟

数据结构与算法图论

1806 字

最短路如何判断是否有负环：f[i][i]<0，

floyd算法#

特点

复杂度比较高，但常数小，容易实现（只有三个for）
适用于任何图，不管有向无向，边权正负，但是最短路必须存在，不能有负环 代码

CPP

for (int k=1;k<=n;k++){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
		//i到j的最短路径等于i到k的最短路径加上k到j的最短路径
			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
		}
	}
}

应用一

P6175 无向图的最小环问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给一个正权无向图，找一个最小权值和的环。首先这一定是一个简单环。想一想这个环是怎么构成的。考虑环上编号最大的结点。f[u-1][x][y] 和 (y,u)，(u,x) 共同构成了环。在 Floyd 的过程中枚举u，计算这个和的最小值即可，时间复杂度为O(n^3)

CPP

long long int d=INF;
	for (int k=1;k<=n;k++){
		//这里算是区间dp求环最小值
		for (int i=1;i<k;i++){
			for (int j=i+1;j<k;j++){
				d=min(d,dis[i][j]+mp[j][k]+mp[k][i]);	
			}
		}
		//这里是floyd求最短路
		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]);
				dis[j][i]=dis[i][j];
			}
		}
	}

应用二 已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通。

该问题即是求 图的传递闭包。我们只需要按照 Floyd 的过程，逐个加入点判断一下。只是此时的边的边权变为 1/0，而取 min 变成了或运算。再进一步用 bitset 优化，复杂度可以到 O(n^3/w)。

CPP

for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
        if(g[i][k]){
        	g[i] |= g[k];
		}     
	}
}        
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++){
    	 cout << g[i][j] << ' ';
	} 
    cout << '\n';
}

Dijkstra算法#

不适用 有负数权值的边

暴力不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在 T 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 O(m)，1 操作总时间复杂度为O(n^2)，全过程的时间复杂度为 O(n^2 + m) = O(n^2)。

CPP

int dis[maxn],vis[maxn];//dis[i]到i的最短路径，vis[i]=true找到了到i的最短路径
void dij(int n,int s){//一共n个节点，从s节点开始
	memset (dis,INF,sizeof (dis));
	dis[s]=0;
	for (int i=1;i<=n;i++){
		int u=0,mind=INF;
		for (int j=1;j<=n;j++){//找到这一轮的最短路节点
			if (!vis[j]&&dis[j]<mind){
				u=j;
				mind=dis[j];
			}
		}
		vis[u]=true;//到u这个点的最短路找到了
		for (int v=head[u];~v;v=edge[v].next){//遍历u的后驱维护dis
			dis[edge[v].v]=min(dis[edge[v].v],dis[u]+edge[v].w);
		}
	}
}

优先队列

二叉堆：每成功松弛一条边 (u,v)，就将v插入二叉堆中（如果 v 已经在二叉堆中，直接修改相应元素的权值即可），1 操作直接取堆顶结点即可。共计O(m) 次二叉堆上的插入（修改）操作，O(n) 次删除堆顶操作，而插入（修改）和删除的时间复杂度均为 O(logn)，时间复杂度为 O((n+m)logn) = O(mlogn)。
优先队列：和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 O(m) 的，时间复杂度为 O(mlogm)。

CPP

#define ll long long
struct node {
    ll dis,u;

};
//dis的小根堆
bool operator < (const node &a,const node &b){
    return a.dis>b.dis;
}
ll dis[maxn],k=0;//dis表示最短路的长度，k表示已经找到的最短路的节点个数
bool vis[maxn];
priority_queue <node> q;
void dij(ll n,ll s){
	memset (dis,0x3f,sizeof (dis));
    q.push({0,s});
    dis[s]=0;

    while (!q.empty()){
        if (k>=n){
            break;
        }
        ll u=q.top().u;
        q.pop();
        if (!vis[u]){
            vis[u]=true;
            k++;
            for (int v=head[u];~v;v=edge[v].next){
                if(!vis[edge[v].v]) {
                    dis[edge[v].v]=min(dis[edge[v].v],dis[u]+edge[v].w);
                    q.push({dis[edge[v].v],edge[v].v});
                }

            }
        }
    }
    return ;
}

Bellman–Ford 算法#

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

[[判断是否有负环#处理图中存在环的最短路径算法|Bellman–Ford 算法如何判断是否有负环]] 需要注意的是，以s点为源点跑Bellman–Ford算法时，如果没有给出存在负环的结果，只能说明从s点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行Bellman–Ford算法。

过程 Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是 O(m) 的，那么最多会循环多少次呢？在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 +1，而最短路的边数最多为 n-1，因此整个算法最多执行 n-1轮松弛操作。故总时间复杂度为 O(nm)。

代码

CPP

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

vector<Edge> edge;

int dis[MAXN], u, v, w;
const int INF = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  bool flag = false;  // 判断一轮循环过程中是否发生松弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int j = 0; j < edge.size(); j++) {
      u = edge[j].u, v = edge[j].v, w = edge[j].w;
      if (dis[u] == INF) continue;
      // 无穷大与常数加减仍然为无穷大
      // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        flag = true;
      }
    }
    // 没有可以松弛的边时就停止算法
    if (!flag) {
      break;
    }
  }
  // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
  return flag;
}

队列优化：SPFA

很多时候我们并不需要那么多无用的松弛操作。

很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

SPFA 也可以用于判断 s点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s 点可以抵达一个负环。

CPP

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;//vis==1表示这个点被松弛过了，一个点可能被松弛多次
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

最短路

https://www.zzoce.com/blog/求图上最短路/