最短路径

计算图的最短路径有几种经典的算法：

1. 弗洛伊德（Floyd）算法
2. 迪杰斯特拉（Dijkstra）算法
3. 贝尔曼福德（Bellman-Ford）算法
4. SPFA 算法

弗洛伊德算法

弗罗伊德算法的思想来自于动态规划。

基本思路为：

1. 我们知道若给定任意结点 A、B，若想使两点之间的距离减小只有引入第三个点。
2. 首先引入 结点 1 ，是否能使任意两个结点之间距离缩短呢？若能则更新距离。接着引入 结点 2 ，是否能在结点 1 的基础上继续缩短距离呢？这样一直到 结点 N。
3. 因为每次引入 结点 i+1 都是在 结点 i 的基础上，所以最终的结果就是任意两点间的最短距离。

算法模板：

cin>>n>>m;
//n为节点数，m为路径数

for(i=0;i<m;i++){
    cin>>begin>>end>>len;
    route[begin][end]=len;
    //读入路径
}

for(int k=1;k<=n;++k){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(route[i][j]>route[i][k]+route[k][j])
                route[i][j]=route[i][k]+route[k][j];
                //更新距离
        }
    }
}

算法评价：

• 该算法的思想比较简单，但时间复杂度较高。
• 该算法可以处理负边权的问题，但是没法解决负回路的问题。PS：负回路其实也不存在最短路径。
• 除此外，该算法求出的是任意两点间的最短路径，所以是多源的最短路径。

---

迪杰斯特拉算法

迪杰斯特拉算法是基于贪心策略的。

基本思路为：

1. 取所有路径中到源点最近且没有被访问过的一个，加入到已访问节点集合中。
2. 取到的新节点 S 是否会使 S 的邻接节点到源点的距离缩短，若可以则更新距离。
3. 循环步骤 2，直至所有节点已经全部被访问到。这时所有点到源点的最短距离即确定。

算法模板：

cin>>n>>m;
//n为节点数，m为路径数
for(i=1;i<=n;i++)
{
    dis[i]=inf
    //初始化路径为无穷大
    book[i]=0
    //所有节点的访问状态皆为未访问
}
for(i=0;i<m;i++){
    cin>>begin>>end>>len;
    route[begin][end]=len;
    //读入路径
}
for(i=1;i<=n;i++){
    dis[i]=route[1][i];
}
book[1]=1;
//初始化起点状态
for(i=1;i<=n;i++){
    min=inf;
    for(j=1;<=n;j++){
        if (book[j]==0 && dis[j]<min){
            min=dis[j];
            u=j;
        }
    }
    book[u]=1;
    //找到距离最小的节点
    for(j=1;j<=n;j++){
        if(book[j]==0 && route[u][j]!=inf){
            if(dis[j]>dis[u]+route[u][j])
                dis[j]=dis[u]+route[u][j]
                //更新未访问节点的最短距离
        }
    }
}

算法评价：

• 当所有边权为正时，由于是按距离顺序由小到大选出的结点，所以后面出现的结点的距离，本身就比前面的结点距离大，加入他们不会影响已经确定距离的结点。这保证了算法的正确性。
• 但也正因为这样，这个算法不能处理负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路程不会改变的性质。

---

贝尔曼福德算法

贝尔曼福德算法则是基于动态规划的思想。在存储路径时使用的是邻接表而非临界矩阵。贝尔曼福德算法可以解决迪杰斯特拉算法不能解决的负边权问题。

基本思路为：

1. 同样需要一个 dis 数组来记录距离，除此外还需要一个二维数组存储边的集合，初始时只有源点距离自己距离为 0，其余为 inf 无穷大。
2. 遍历一次所有的边，判断是否可以松弛其余节点的距离 : dis[end]>dis[begin]+len 。第一次松弛的显然是和源点邻接的点的距离。
3. 循环执行步骤 2 N-1 次，直至所有的边都被松弛结束。这相当于将除源点外的每一个点都加入到图中看是否可以松弛路径，这个思想来自于：一条最短路径除源点外最多也就有 N-1 个结点，循环 N-1 遍已经可以将情况考虑全面。
4. 在次基础上可进行剪枝，当一次循环过程中没发生任何距离的变化，说明已经到达最终的状态，可以结束。

算法模板：

for(i=1;i<=n;i++){
    dis[i]=inf;
}
dis[1]=0;

//初始化节点到源点距离
for(i=0;i<m;i++){
    cin>>begin>>end>>len;
    b[i]=begin;
    e[i]=end;
    l[i]=len;
    //读入路径
}
for(k=0;k<n;k++){
    flag=0;
    for(i=0;i<m;i++){
        if(dis[e[i]]>dis[b[i]]+l[i])
            dis[e[i]]=dis[b[i]]+l[i];
            flag=1
    }
    if(flag==0) break;
}

除此之外贝尔曼福德算法还可以，用来判断图中是否存在负权环路，因为如果在 n-1 次松弛之后还可可以继续松弛，意味着一定存在负权回路，因为正权回路只能无端使距离增加，而不是减少。

该算法的不足之处在于：由于某些节点在经过松弛之后，不在受后续松弛的影响，但每次还是要判断是否可以进行松弛，这浪费了时间。

---

SFPA 算法

SFPA 算法是改进后的贝尔曼福德算法，在贝尔曼福德算法的最后，我们总结了该算法的不足，但也同时启发我们，每次只要对发生距离改变的顶点的所有出边进行松弛即可。这里需要用到一个队列对松弛后元素进行存储。

基本思路为：

1. 将源点加入队列。
2. 出队队首元素，分别对其出边进行松弛，若松弛成功，且这条边的终点不在队列中，则将该节点入队。重复执行该操作，直至队列为空。

算法模板为：

queue Q；
for(i=1;i<=n;i++){
    book[i]=0;
    //所有点初始都不在队列中
}

queue.push(1);
book[1]=1;
//源点入队

while(!Q.empty()){
    //结束条件为队列为空
    
    elem=Q.top();
    //队首
    Q.pop();
    book[elem]=0;
    //队首出队
    
    for(i=1;i<=n;i++){
        if(route[elem][i]!=inf && dis[i]>dis[elem]+route[elem][i]){
            dis[i]=dis[elem]+route[elem][i];
            //可以进行松弛
            if(book[i]==0){
                //不在队列中，则入队
                Q.push(i);
                book[i]=1;
            }
        }
    }
   
}

算法评价：

时间复杂度比普通的Dijkstra和Ford低，可以计算负边权问题。是单源最短路径中比较优秀的方法。

SPFA双端队列优化

虽然SFPA是队列优化过的贝尔曼福德算法，但昨天遇到的一道题目，让我意识到该算法可以继续优化。

基本思路

1. 在SFPA的基础上，将队列改为双端队列（使用STL中的deque即可）
2. 队列插入的过程需要先判断一下新结点S和队首元素F的关系：
   • 如果dis[S] > dis[F]则结点插入到队尾
   • 相反结点插入队首

多说一句

1. 需要注意一下，在使用的过程中会遇到一个问题：起始结点出队后，需要将他的邻接点入栈，这时候队列空没法判断队首。那么这时候将结点直接入队就可以了。