最短路问题总结

floyed算法

可以求任意两点的最短路，适合负边权，也可以用于检测任意两点是否连通。算法效率O(N^3)

核心代码：

//d[i][j]表示节点i到j的最短路 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]); 其中k一定是在最外面，理解为什么在最外面是最难，这里利用了动态规划的思想。 理解时可以扩大维度 f[k][i][j]表示i->j经过k的最短路,f[k-1][i][j]表示经过k-1，的最短路 f[k][i][j] = min{f[k-1][i][k],f[k-1][i][k] + f[k-1][k][j]} f[k][i][j] 由公式是有f[k-1][i][j] 转化而来，所以k是阶段。

dijkstra算法（迪杰斯特拉）

贪心思想， 效率是O(N^2)，无法处理负边权，数据用邻接矩阵，用优先队列优化用邻接表。 用dist[i]表示i到起点的距离，vist[i]表示i是否被访问过。 策略是，访问过的节点构成一个集合，每次更新一个点，这个点是剩下的点中到起点最短的点， 将他加入集合，然后由新加的点出发更新剩下的点。因为这里的更新剩下的点所以无法处理负边权 void dijkstra(int start) { for(int i=1;i<=n;i++){ int x; int mi=INF; // 在所有未标号的结点中，选择一个d值最小的点x。 //这里有点贪心的意味，每次找最小值进行走下一步。所以可以用堆来优化查找最小值 for(int j=1;j<=n;j++) if(vist[j] == 0 && dist[j] < mi ) //如果j没访问，并且圆点到这个点的距离小于最小值 {x = j ; mi = dist[x];} vist[x] = 1;//这个点标记访问 for(int j=1;j<=n;j++)//从x出发到其他点，更新其他点 if(dist[x] + g[x][j] < dist[j]) //源点经过x到j 的距离小于其他路到j 的距离 { dist[j]=dist[x] + g[x][j];//更新 path[j]=x;//j经过x } } }

bellman-ford算法

松弛原理，效率O(NV),可以处理负边权，也可以判断是否用负权回路。采取边目录储存 bellman-ford的理论： 对于不存在负权回路的图，意味着，最短路最多（不算起点）只经过n-1个节点。 那么就可以通过n-1次松弛操作就可以得到最短路 //采取边目录的储存方式，E[i]表示第i条边 void b_ford(int start){ dist[start]=0; for(int i=1;i<n;i++){ for(int j=1;j<=m;j++){//m是边数 if(dist[E[j].x] + w[j] < dist[E[j].y]) //dist[E[j].x]表示边j的第一个点到起点的长度 { dist[E[j].y]= dist[E[j].x] + w[j]; } if(dist[E[j].y] + w[j] < dist[E[j].x]) //dist[E[j].y]表示边j的第2 个点到起点的长度 dist[E[j].x]= dist[E[j].y] + w[j]; //这道题是无向图，所以每个边要判断两次，对于有 向图则是一次 //write(n); } } //这里可以在对每个边判断是否还能不能松弛，如果还能松弛，说明有负权回路 }

SPFA!

SPFA是使用队列实现的Bellman-Ford算法。邻接表存储（） 每次从源点对连接他所有边（u，v）进行松弛，如果能够松弛，说明v可以修改，则将v压入松弛队列 操作步骤：

1. 初始队列和标记数组 2. 源点入队。 3. 对队首点出发的所有边进行松弛操作（即更新最小值）。 4. 将不在队列中的尾结点入队。 5. 队首点更新完其所有的边后出队。

queue<int> q; bool inqueue[N]; // 是否在队列中 int cnt[N]; // 检查负环时使用：结点进队次数。如果超过n说明有负环。 bool SPFA(int start) { // 有负环则返回false // 初始队列和标记数组 for (int i=0; i<n; i++) d[i]=INF; d[start]=0; memset(cnt,0,sizeof(cnt)); q.push(start); // 源点入队 cnt[start]++; while (!q.empty()) { int x=q.front(); q.pop(); inqueue[x]=false; // 对队首点出发的所有边进行松弛操作（即更新最小值） for (edge *e=adj[x];e!=NULL;e=e->next){ int &v=e->v, &w=e->w; if (d[v]>d[x]+w) { d[v] = d[x]+w; // 将不在队列中的尾结点入队 if (!inqueue[v]) { inqueue[v]=true; q.push(v); if (++cnt[v]>n) return false; // 有负环 } } } } return true; }