Floyd算法

使用条件

可以求出多源最短路，可以处理负权边的情况，但是不能出现负环。

时间复杂度

O（n3）

讲解

Floyed算法使用的是动态规划的方法。

只需要使用最简单粗暴的做法，将出发点、结束点、中转点都枚举一遍就可以了。

状态转移方程：

1
d[i][j]=min(d[i][k]+d[k][j],d[i][j])

这样，再写出Floyd算法的核心代码就很容易了。

另外需要注意的是：Floyd算法不能解决带有负权回路（或者叫负权环）的图，因为带有负权回路的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有负权回路那么这个图则没有最短路。

核心代码

1
2
3
4
for(k=1;k<=n;k++) //枚举中转点
    for(i=1;i<=n;i++) //枚举起点        
        for(j=1;j<=n;j++)          //枚举终点
            d[i][j]=min(d[i][k]+d[k][j],d[i][j]);

Dijkstra算法

使用条件

求单源最短路径，不能处理负权。

时间复杂度

O（n2）

讲解

Dijkstra算法使用的是贪心方法，d[i]表示起点s0到i的最短距离。

从起点s0开始，选择未访问过的离s0最近的一个点i，也就是最小的d[i]，因为所以边权为正，不会存在更短的路径到达i，保证了贪心的正确性。然后将i作为中间点，更新经过i可到达的点的最短路距离，继续贪心寻找未访问过的最近的一个点，经过n次贪心，算法结束。

看图：

根据这个图，Dijkstra算法应该就很好理解了。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (i = 1; k <= n; k++)
{
    maxn = 0x7fffffff;
    for (j = 1; j <= n; j++)                 //找出未访问最小的d[j]
    {
        if (!vis[j] && d[j] < maxn)
        {
            maxn = d[j];
            k = i;
        }

    }
    vis[k] = 1;
    for (j = 1; j <= n; j++)          //k作为中间点，更新起点经过k到达其他点的d[j]
        if (w[k][j])
        {
            d[j] = min{ d[k] + w[k][j],d[j] };
        }
}

SPFA算法

使用条件

求单源最短路，可以处理负权边

时间复杂度

对于稀疏图，为O(km)，k为较小的常数，而对于稠密图或者构造的网格图，会提高到O(n*m)

讲解

建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

图：

源点A首先入队，并且AB松弛

在这里插入图片描述

扩展与A相连的边，B，C 入队并松弛。

在这里插入图片描述 在这里插入图片描述

D出队，E入队并松弛。

在这里插入图片描述

E出队，此时队列为空，源点到所有点的最短路已被找到，A->E的最短路即为8

在这里插入图片描述

以上就是SPFA算法的过程。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
q.push(s);
vis[s]=1;  //源点s入队，标记入队
while(q.size())
{
       u=q.front();q.pop();vis[u]=0;        //取出队头，标记未入队
       for(i=head[u];i;i=next[i])
       {
              v=ver[i];
              w=edge[i];
              if(dis[u]+w<dis[v])
              {
                     dis[v]=dis[u]+w;
                     if(!vis[v])   {q.push(v);vis[v]=1;}    //如果没有在队列，入队，标记已入队
              }    
       }
}