最短路径
所谓最短路径, 就是求一个图 (无向或有向都行) 每个点到每个点的最短路
Floyd
所谓 Floyd, 其实原理很简单, 假设 i 点到 j 点的最短路用 f[i][j]代替, 那么若 i 点到 j 点有路就存进 f[i][j]里, 没有路就令 f[i][j]=2147483647 注意 f 数组需要开 longlong
那么要求 f[i][j]的最短路, 我们需要枚举一个点 k, 这里需要保证 i!=j, i!=k, j!=k. 若我们从 i 点绕 k, 再从 k 点到 j 点需要走的长度比直接从 i 点到 j 点的路径要长, 那么就更新 f[i][j]的最短路: f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
整个 Floyd 的速度在 O(n^3)
- for(int k=1;k<=n;k++)
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)//k 一定要写在最前面
- if(i!=j&&i!=k&&j!=k)// 不相同
- f[i][j]=min(f[i][j],f[i][k]+f[k][j]);// 比对最短路
- dijkstra
所谓 dijkstra, 其实原理很简单, 我们假设 i 点直接 j 点用 f[i][j]代替 (与 Floyd 相同), 那么若 i 点到 j 点有路就存进 f[i][j] 里, 没有路就令 f[i][j]=2147483647 注意 f 数组需要开 longlong
dijkstra 求的是给出一个点, 求这个点到其他点的最短路, 这个最短路我们用 dis 数组表示(不是 diss 的意思). 我们还需要一个 visit 数组, 它究竟指什么意思呢, 待会再讲.
接下来我们需要在这 n 个点里找目前离它最近的点, 并且保证这个点我们没有它与其他点进行求最短路的操作, 例如我们找到了 j 点, 它是目前离 i 最近, 且没有它与其他点进行求最短路的操作, 那么最小值 mi 值等于 dis[j], 利用一个指针 p 指向当前的 j 点. 而没有它与其他点进行求最短路的操作的判断就用 visit 数组记录 false 或 true
然后我们要进行求最短路的操作, 枚举所有的点, 只要 dis[p]+f[p][j]<dis[j]及起点到 p 点的最小值加上 f 数组里记录的 p 点到 j 点的路径长度, 若比起点到 j 点的最小值更好 (小), 就更新 dis[j] 的值: dis[j]=dis[p]+f[p][j]
重复以上操作即可.
再说说为什么要目前离它最近的点, 并且保证这个点我们没有它与其他点进行求最短路的操作, 因为 dijkstra 就是利用一个点, 一个局部扩展到全局的最短路, 最优解, 所以它需要像递推一样通过局部发展到全局.
整个 dijkstra 的速度在 O(n^2)
- int dijkstra()// 这里可以用 void
- {
- for(int i=1;i<=n;i++)
- dis[i]=f[1][i],visit[i]=0;// 每一次操作都需要初始化, 一般来说起始点都应该是 1
- for(int i=1;i<=n;i++)
- {
- mins=2147483647;
- p=0;
- for(int j=1;j<=n;j++)
- {
- if(visit[j]==0&&dis[j]<mins)
- {
- mins=dis[j];
- p=j;
- }
- }// 找最小值, 以及这个点没有进行操作
- if(p==0)break;// 全图已经遍历, 退出
- visit[p]=1;// 标记这个点已遍历
- for(int j=1;j<=n;j++)// 枚举全图的点
- if(p!=j&&dis[p]+f[p][j]<dis[j])
- dis[j]=dis[p]+f[p][j];// 可以就更新最小值
- }
- return dis[n];// 这里一般返回终点
- }
- SPFA
所谓 SPFA, 就是最短路径快速算法是 Shortest Path Faster Algorithm 的缩写.
很多时候, 给定的图存在负权边, 这时类似 Dijkstra 等算法便没有了用武之地, SPFA 算法便派上用场了. SPFA 的复杂度大约是 O(kE),k 是每个点的平均进队次数(一般的, k 是一个常数, 在稀疏图中小于 2).
但是, SPFA 算法稳定性较差, 在稠密图中 SPFA 算法时间复杂度会退化.
实现方法: 建立一个队列, 初始时队列里只有起始点, 在建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值, 该点到他本身的路径赋为 0). 然后执行松弛操作, 用队列里有的点去刷新起始点到所有点的最短路, 如果刷新成功且被刷新点不在队列中则把该点加入到队列最后. 重复执行直到队列为空.
此外, SPFA 算法还可以判断图中是否有负权环, 即一个点入队次数超过 N.
给定一个有向图, 求 A~E 的最短路.
源点 A 首先入队, 并且 AB 松弛
扩展与 A 相连的边, B,C 入队并松弛.
B,C 分别开始扩展, D 入队并松弛
E 出队, 此时队列为空, 源点到所有点的最短路已被找到, A->E 的最短路即为 8
以上就是 SPFA 算法的过程.
期望的时间复杂度 O(ke)
- bool spfa(int x)// 返回的是真就不是负环, 否则就是负环
- {
- int t,temp;
- queue<int>q;
- for(int i=1;i<=n;i++)
- dis[i]=2147483647,visit[i]=false,In[i]=0;// 初始化, In 判断是否负换
- dis[x]=0,visit[x]=1;q.push(x);// 入队
- while(!q.empty())// 还没遍历完
- {
- t=q.front();q.pop();// 求头值, 弹出头值
- visit[t]=false;// 假设这个点还没有操作
- for(int i=0;i<=f[t].size()-1;i++)// 它所有能到的点
- {
- temp=f[t][i].to;// 到达的地方
- if(dis[temp]>dis[t]+f[t][i].len)// 能否松弛
- {
- dis[temp]=dis[t]+f[t][i].len;// 松弛
- if(!visit[temp])// 只要没搜过 temp
- {
- q.push(temp);// 入队
- visit[temp]=true;// 它已经入队了
- if(++In[temp]>n)return false;// 负环判断
- }
- }
- }
- }
- return true;// 不是负环, 真
- }
ps: 感谢一些大佬提供的博客以及题解, 这里有参考以及借用
最短路径
来源: http://www.bubuko.com/infodetail-3062534.html