一直想整理一下最短路，好久之前学的（都忘了差不多了），再回顾一下，增加印象

最短路；

1.Floyd最短路算法；

（被戏称为五行算法）它可以求出一个图中任意两点之间的最短路距离，即多源最短路算法，但是复杂度为O(n3)很大，所以一般比赛用到的机会很少，1s的时间要求下，最多只能求1000点之间的最短路。优点就是代码短，好理解。

主要思想就是用图中的一个点k来判断能不能优化i到j之间的最短距离。（枚举k点）。

代码：

void floyd()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                lu[i][j]=min(lu[i][j],lu[i][k]+lu[k][j]);
}

很好理解吧，就是枚举中间点 k，看 k 能不能优化 i 到 j 的最短路。

2.dijstra最短路算法

（被称为最常用的最短路算法），复杂度O（n2)，虽然还是不怎么低，但是解决大部分的最短路题还是可以的。这个算法可以求一个点到任何点的最短路距离，即单源最短路算法。但是不能求存在负权边的情况。

主要思想就是；把点分为两类，一类是已经确定的最短路径的点（标记点），一类是还没有确定最短的点（未标记点），每次用这个已经找到的标记点来拓展未标记点，比如；b点是你已经找到的标记点，然后我发现找到最小的（含标记点）的边有个e[b][c]，那么dis[c]的最短路距离就知道了dis[c]=dis[b]+e[b][c]，（dis[i]表示为0点到i点的最短距离）。然后c就变成了标记点。但是此时只是在目前dis[c]是最短，但后面还有边的时候dis[c]可能还能更新更短。所以没到结束dis[i]都不一定是最短的。就这样我们一直找未标记点，一直到最后一个，找完了之后,此时dis[i]才真正是0到i点的最短距离。

代码：

核心代码：
for(int i=1;i<=n;i++)
   {
       mark[i]=0;
       dis[i]=e[1][i];
   }
   mark[1]=1;
    int minn,u;
    for(int i=2;i<=n;i++)
    {
        minn=0x3f3f3f3f;
        for(int k=1;k<=n;k++)
        {
            if(mark[k]==0&&minn>dis[k])
            {
                minn=dis[k];
                u=k;
            }
        }
        mark[u]=1;
        for(int j=1;j<=n;j++)
        {
            if(mark[j]==0&&dis[j]>dis[u]+e[u][j])
            {
                dis[j]=dis[u]+e[u][j];
            }
        }
    }

3,spfa最短路算法：

spfa算法就是队列优化过后的Bellman-Ford算法，复杂度和边有关，所以适用于稀疏图，O（KE），K一般为二，E为这个图的边的数量。也是单源最短路算法。spfa是可以处理负权边存在的情况的。

主要思想：用邻接表建图，先存一个首节点到栈中，然后出栈对这个节点的所以边遍历，优化每一个点到首节点的最短距离，没有进过栈的点进到栈中，直到栈空；

void spfa() {
    int u,l=0,r=1;
    que[1]=s;//spfa的初始化
    vis[s]=1;
    dis[s]=0;
    while(l<r){
        u=que[++l];
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            if(dis[edge[i].to]>dis[u]+edge[i].val){//如果这个点的下一个点的最短距离大于头指针指向的点的最短路径加上他们之间的距离则更新。
                dis[edge[i].to]=dis[u]+edge[i].val;
                if(!vis[edge[i].to]){//避免重复入队。
                    vis[edge[i].to]=1;
                    que[++r]=edge[i].to;
                }
            }
        }
    }
}