啊哈算法（6）——最短路径

柔光的暖阳◎ 2022-05-15 05:44 225阅读 0赞

**最短路径**  
问题：对于一个给定的的图求出任意两点之间的最短路径？  
可以通过DFS或者BFS求出两个点之间的最短的路径，在本节介绍其他的算法来求出两个点之间的最短路径。  
1、Floyd-Warshall（不能解决带负权环路的图）  
思想：若要让两个顶点之间的距离变小，只有通过一个顶点中转，甚至可能经过多个顶点中转，假定输入如下：

4 8
    1 2 2
    1 3 6
    1 4 4
    2 3 3
    3 1 7
    3 4 1
    4 1 5
    4 3 12

输入一个n个顶点m条边的图，接下来m行形如“a b c”表示a到b路径为c。Floyd-Warshall实现如下：

#include<iostream>
    
    using namespace std;
    
    #define MAX 99999
    int main()
    {
        int e[10][10] = {
       0};//用来存储边的信息。
        int n, m;
        cin >> n >> m;
    
        //图的初始化 采用邻接矩阵的方式存储图
        for(int i=1;i<=n;++i)
            for (int j = 1; j <= n; ++j)
            {
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = MAX;
            }
        int a, b, c;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a >> b >> c;
            e[a][b] = c;
        }
    
        //Folyd-Warshall算法核心语句  第一趟相当于得到了通过一号节点中转的路径长度
        for (int k = 1; k <= n; ++k)   //通过节点中转，第一趟通过1号节点中转，以此类推
        {
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= n; ++j)
                {
                    if ((e[i][k]< MAX) && (e[k][j] < MAX) && (e[i][j] > e[i][k] + e[k][j]))
                        e[i][j] = e[i][k] + e[k][j];//更新
                }
            }
        }
    
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cout << i << " " << j << " "<<e[i][j]<<endl;
            }
        }
        system("pause");
    }

2、Dijkstra算法（不能解决带负权值的图）  
问题：解决指定一个点（源点）到其余各个顶点之间的最短路径。  
使用一个数组dis\[\]存储源点到各个顶点的距离，初始值为初始的路径，算法的基本思想为：每一次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终找到源点到其余顶点的最短路径。步骤如下：

1.  将所有的顶点分为两部分：已知最短路程的顶点集合p和未知最短路程的顶点集合Q。最开始已知最短路程的顶点集合P中只有源点一个顶点。在这里使用一个book\[\]数组用来记录哪些顶点在集合P中。
2.  设置源点到自己的最短路程为0即dis\[s\]=0。若有源点可以直接到达的顶点i，则把dis\[i\]设置为e\[s\]\[i\]否则设置为无穷大（即不可到达的顶点）。
3.  在集合Q的所有定点中选择一个离源点s最近的顶点u（此时dis\[u\]最小，因为不可能再通过其他的顶点中转使得其变小）加入到集合P。并且考察所有以点u为起点的边，对每一条边进行松弛操作。例如：存在一条从u到v的边，那么可以通过将边u->v添加到尾部来拓展出一条从s到v的路径，这条路程的长度为dis\[u\]+e\[u\]\[v\]。如果这个值比dis\[v\]的值还要小，可以用新值来代替dis\[v\]中的值。
4.  重复上述第三步，如果集合Q为空，算法结束。最终dis数组中就是源点到所有点的最短路程。  
    假定如下输入：

6 9
    1 2 1
    1 3 12
    2 3 9
    2 4 3
    3 5 5
    4 3 4
    4 5 13
    4 6 15
    5 6 4

采用邻接矩阵来存储图，Dijkstra算法实现如下：

#include<iostream>
    
    using namespace std;
    
    #define MAX 99999
    int main()
    {
        int e[10][10] ;//用来存储边的信息。
        int book[10];//用来标记是否在集合P中
        int dis[10];//用来存储源点到各个顶点的最短距离
    
        int n, m;
        cin >> n >> m;
    
        //图的初始化 采用邻接矩阵的方式存储图
        for(int i=1;i<=n;++i)
            for (int j = 1; j <= n; ++j)
            {
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = MAX;
            }
        int a, b, c;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a >> b >> c;
            e[a][b] = c;
        }
    
        //初始化dis数组，假定源点为1号顶点
        for (int i = 1; i <= n; ++i)
        {
            dis[i] = e[1][i];
        }
    
        //初始化标记数组
        for (int i = 1; i <= n; ++i)
        {
            book[i] = 0;
        }
        book[1] = 1;   //初始源点在p集合中
    
        //Dijkstra算法核心
        for (int i = 1; i <= n; ++i)
        {
            //在集合Q中找到到一号顶点最近的点
            int min = MAX;
            int u = 0;
            for (int j = 1; j <= n; j++)
            {
                if (book[j] == 0 && dis[j] < min)
                {
                    min = dis[j];
                    u = j;
                }
            }
            book[u] = 1;//将找到的顶点加入集合P中
    
            //通过节点u为中心来进行扩展
            for (int v = 1; v <= n; ++v)
            {
                if (e[u][v] < MAX&&book[v]==0)
                {
                    if (dis[v] > dis[u] + e[u][v])  //通过节点u来进行松弛
                        dis[v] = dis[u] + e[u][v];
                }
            }
        }
    
        for (int i = 1; i <= n; i++)
        {
            cout << dis[i]<<" ";
        }
        system("pause");
    }

算法复杂度：这个算法的时间复杂度为O(N^2)，每一次找到离源点最近的点时间为O(N)，这里可以使用堆来进行优化，使得这一部分时间的复杂度降到O(logN)。另外对于边数M远少于N^2的稀疏图来说，可以使用邻接表的方式来存储整个图，使整个的时间复杂度优化到O((M+N)logN)，当然在最坏的情况下M=N^2。下面介绍使用数组来实现邻接表（没有真正的使用指针，链表）。  
首先为每一条边进行（1~m）编号。用u，v，w三个数组来记录每条边的信息，即u\[i\]、v\[i\]和w\[i\]表示第i条边从u\[i\]号顶点到v\[i\]号顶点，并且权值为w\[i\]。first数组的1~n号单元格分别来存储1~n号顶点的第一条边的编号，初始没有加入边所以都为-1。即first\[u\[i\]\]保存了顶点u\[i\]的第一条边的编号，next\[i\]存储的编号为i的边的下一条边的编号。例如给出如下输入：

4 5
    1 4 9
    2 4 6
    1 2 5
    4 3 8
    1 3 7

采用邻接表的方式存储，实现如下：输出与读入的顺序相反，可以理解为每一次网“链表的头插入”

#include<iostream>
    
    using namespace std;
    
    int main()
    {
        //u[i]->v[i],w[i]表示第i条边是顶点u[i]到顶点v[i]并且权值为w[i]
        int u[6], v[6], w[6];
    
        //first[i]表示顶点i的第一条边的编号,next[i]表示编号为i的边的下一条边的编号
        int first[5], next[6];
    
        int n, m;//顶点数目和边的数目
    
        cin >> n >> m;
    
        //first初始设为-1
        for (int i = 1; i <= n; ++i)
        {
            first[i] = -1;
        }
    
        //按顺序读入边数
        for (int i = 1; i <= m; ++i)
        {
            cin >> u[i] >> v[i] >> w[i];
    
            //更新first和next
            next[i] = first[u[i]];
            first[u[i]] = i;  //顶点u[i]的第一条边的编号为i
        }
    
        //遍历每一条边
        for (int i = 1; i <= n; ++i)
        {
            int k = first[i];  //节点i的第一条边的编号
            while (k != -1)
            {
                cout << u[k] << " " << v[k] << " " << w[k] << endl;
                k = next[k];
            }
        }
        system("pause");
    }

3、Bellman-Ford（解决负权边）  
Dijkstra算法和Floyd\_Warshall都不可以解决带负权边的图，这里介绍的Bellman-Ford可以很好的解决带负权边的问题，且实现简单。  
算法代码为：

for(int k=0;k<n-1;++k)
        for(int i=1;i<=m;++i)
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];

使用一个diss数组来存储源点到各个顶点之间的距离与dijkstra算法中的diss数组一样，将其初始化(除了源点意外，其余都初始化为无穷大)，采用邻接表的方式来存储这个地图。

if(dis[v[i]]>dis[u[i]]+w[i])
        dis[v[i]]=dis[u[i]]+w[i];

这是算法的核心思想。意思是看看能否通过u\[i\]->v\[i\]这条边，使得源点到v\[i\]顶点的距离变短，这一点与dijkstra算法是一样的，我们需要把所有边都松弛一变，所以要经过m次。其实就是说，经过第一轮的松弛之后，得到的是源点只能经过一条边到达其余各顶点的最短路径，进行k轮就是源点最多经过k条边到达各个顶点的最短路程。那么一共需要经过多少轮？只用进行n-1轮，因为在一个含有n个节点的图中，任意两点之间的最短距离最多包含n-1条边。（假如最短路径中含有回路，那么若回路为正权回路，就一定会存在更短的路径；若为负权环路，那么就不存在最短路径，所以若存在最短路径最多包含n-1条边）  
对于如下样例：

5 5
    2 3 2
    1 2 -3
    1 5 5
    4 5 2
    3 4 3

对应的最短路径算法Bellman-Ford实现代码如下：

/*Bellman-Ford*/
    
    #include<iostream>
    #define inf 99999
    using namespace std;
    
    int main()
    {
    
        int dis[10]; //用来存储源点到各个顶点的最短距离
        int bak[10];
    
        int u[10], v[10], w[10];//用来存储每条边的信息
        int n, m;
        int flag = 0;//用于检测图中是否带有负权回路
        cin >> n >> m;
    
        int a, b, c;
        for (int i = 1; i <= m; ++i)
            cin >> u[i] >> v[i] >> w[i];
    
        //初始化dis数组，此时表示经过0条边，到达其余点的最近距离，所以除了源点外，其余初始化为无穷大
    
        for (int i = 1; i <= n; ++i)
            dis[i] = inf;
        dis[1] = 0;
    
        //bellman-ford算法核心语句
        for (int k = 1; k < n; ++k)//最多经过n-1轮松弛
        {
            for (int i = 1; i <= n; i++)
                bak[i] = dis[i];        //dis数组备份用于判断看是否可以提前结束
    
            for (int i = 1; i <= m; ++i)
                if (dis[v[i]] > dis[u[i]] + w[i])
                    dis[v[i]] = dis[u[i]] + w[i];
    
            //松弛完毕后检查dis数组是否更新
            int check = 0;
            for(int j=1;j<=n;++j)
                if (bak[j] != dis[j])
                {
                    check = 1;
                    break;
                }
            if (check == 0)
                break;             //如果dis数组没有更新 可以提前退出，结束算法
        }
    
        //检测负权回路 如果在进行n-1轮之后还可以松弛那么说明，图中带有负权回路
        for(int i=1;i<=m;++i)
            if (dis[v[i]] > dis[u[i]] + w[i])
            {
                flag = 1;
                break;
            }
    
        if (flag == 1)
        {
            cout << "带有负权回路" << endl;
        }
        else
        {
            //输出结果
            for (int i = 1; i <= n; ++i)
                cout << dis[i] << " ";
        }
        system("pause");
    }

Bellman-ford算法可以检测图中是否带有负权回路：检测负权回路 如果在进行n-1轮之后还可以松弛那么说明，图中带有负权回路

4、Bellman-ford算法的队列优化  
Bellman-ford算法中在没进行松弛之后就有一些顶点已经求得了最短路程，它的最短路程不会再受后续松弛的变化，所以每一次松弛只对最短路径估计值发生了变化的点进行松弛，使用队列优化。  
算法过程：每一次选取队列的首顶点u，对顶点u的所有出边进行松弛操作。例如有一条u->v的边，当这条边可以使得源点到顶点v的最短路程变短，并且顶点v不在队列中就将其加入队列。（同一个顶点在队中出现多次毫无意义，所以需要使用一个数组来判重）。对顶点u的所有边判断完毕之后就可以将其出对，直到队列为空为止。  
对于如下输入：

5 7
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 4 4
    4 5 5
    5 3 6

使用邻接表来存储这个图，对应的算法实现为：

/*Bellman-ford队列优化算法*/
    #include<iostream>
    #define inf 999999
    
    using namespace std;
    
    int main()
    {
        int u[8], v[8], w[8];//用来存储边的信息 数组大小m+1；
        int first[6];//存储节点i的第一条边的编号，数组大小为n+1;
        int next[8];// 存储编号为i的边，下一条边的编号
        int dis[6] = { 0 }, book[6] = { 0 };//book数组用来标记 顶点是否在队列中
        int que[101] = { 0 };
        int n, m;
        cin >> n >> m;
    
        //初始化
        for (int i = 1; i <= n; ++i)
            first[i] = -1;
    
        //读入边
        for (int i = 1; i <= m; ++i)
        {
            cin >> u[i] >> v[i] >> w[i];
            next[i] = first[u[i]];
            first[u[i]] = i;
        }
    
        //初始化dis数组
        for (int i = 1; i <= n; ++i)
            dis[i] = inf;
        dis[1] = 0;
    
        //初始化book数组，刚开始都没有入队所以都初始化为0
        for (int i = 1; i <= n; ++i)
            book[i] = 0;
    
        int head = 1, tail = 1;
        //源点入队
        que[tail] = 1;
        tail++;
        while (head<tail)
        {
            int k = first[que[head]];  //对首顶点的第一条边
            while (k != -1)           //判断改顶点的所有出边
            {
                if (dis[v[k]] > dis[u[k]] + w[k])   //判断是否松弛成功
                {
                    dis[v[k]] =dis[u[k]] + w[k];//更新源点到顶点v[k]的距离
    
                    if (book[v[k]] == 0)        //不在队列中就将其入队
                    {
                        que[tail] = v[k];
                        tail++;
                        book[v[k]] = 0;
                    }
                }
                k = next[k];//判断下一条边
            }
            //出对
            book[que[head]] = 0;
            head++;
        }
    
        for (int i = 1; i <= n; ++i)
            cout << dis[i] << " ";
    
        system("pause");
    }

使用队列优化的Bellman-ford算法在形式上和广度优先搜索非常类似，但是不同的是在这里很可能在出对之后再次被放入队列，也就是当一个顶点的最短路程估计值变小之后，需要对所有的出边进行松弛，但是这个点的估计值再次变小，任然需要对其所有的出边再次进行松弛，这样才能保证相邻顶点的最短路程同步更新。使用一个队列来存放被松弛成功的顶点，之后只对队列中的点进行处理，这就降低了算法时间复杂度，但是在最坏的情况下也是O(MN)。当一个点进入队列的次数超过n次，那么这个图中肯定存在负权环路。

5、最短路径算法总结

*  Floyd算法  
    空间复杂度O(N^2)，时间复杂度O(N^3)，可以解决带负权边的图，但是不能解决带负权回路的图，虽然复杂度较高但是均摊到每一个点上属于较优的。
 *  Dijkstra算法  
    属于一种贪心的算法，每次扩展一个最短路程的点，更新与其相邻点的路程。当所有边的权值都为正时，由于不会存在一个路程更短的没扩展的点，所以这个点的路程不会在改变，但是用本算法求最短路径的图不能有负权边，因为扩展到负权边的时候会产生更短的路程，有可能破坏了已经更新的点的路程不会改变的性质，采用邻接表存图并且使用堆来寻找最短路程时，空间复杂度为O(M)，时间复杂度为O((M+N)logN)。
 *  Bellman-ford算法  
    空间复杂度为O(M)，时间复杂度为O(NM)，可以解决带负权边的图，并且可以判断一个图中是否有负权环路。
 *  Bellman-ford队列优化算法  
    使用队列每一次只是判断松弛成功的顶点，空间复杂度为O(M)，时间复杂度在最坏的情况下为O(MN)，同样可以解决带负权边的图，并且判断一个图中是否有负权环路。