最短路径

最短路径

所谓最短路径，就是求一个图（无向或有向都行）每个点到每个点的最短路

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:感谢一些大佬提供的博客以及题解，这里有参考以及借用

最短路径

原文：https://www.cnblogs.com/kurlisjoey/p/10883653.html