最短路径算法

最短路径问题是图论研究中的一个经典的算法问题，旨在寻找图（由结点和路径组成的）中两个结点之间的最短路径。我们经常使用的最短路径算法有Dijkstra算法，Floyd算法和SPFA算法。

Dijkstra算法

算法思想

• Dijkstra算法适合计算给定起点的最短路径问题；
• 总是寻找距离目前结点集合最近的结点，加入到集合后更新集合外结点到集合的距离进行循环求解；
• Dijkstra同样适合应用于最短路由算法等应用领域。

题目描述

本题目描述引自hihocoder第二十三周hiho一下hiho1081。
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^3，M<=10^4, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
【输出】
对于每组测试数据，输出一个整数Ans，表示从S到T至少要走的路程。
【样例输入】

5 23 5 4
1 2 708
2 3 112
3 4 721
4 5 339
5 4 960
1 5 849
2 5 98
1 4 99
2 4 25
2 1 200
3 1 146
3 2 106
1 4 860
4 1 795
5 4 479
5 4 280
3 4 341
1 4 622
4 2 362
2 3 415
4 1 904
2 1 716
2 5 575

【样例输出】

123

代码实现

#include <iostream>
#include <string.h>
#define N 1005

using namespace std;

int main()
{
    unsigned len[N][N];
    memset(len, -1, sizeof(len));
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    int from, to;
    unsigned length;
    for(int i = 0; i < m; ++i)
    {
        cin >> from >> to >> length;
        length = min(length, len[from][to]);
        len[from][to] = len[to][from] = length;
    }

    int index;
    int value;
    while(1)
    {
        index = 1;
        value = len[s][6];
        for(int i = 2; i <= n; ++i)
        {
            if(value > len[s][i])
            {
                value = len[s][i];
                index = i;
            }
        }

        for(int i = 1; i <= n; ++i)
        {
            if(len[index][i] != (unsigned)-1)
            {
                len[s][i] = min(len[s][index] + len[index][i], len[s][i]);
            }
        }

        if(index == t)
        {
            break;
        }
        else
        {
            len[s][index] = -1;
        }
    }
    cout << len[s][t] << endl;
    return 0;
}

Floyd算法

算法思想

• Floyd算法实质上是一种动态规划的思想；
• 设D[i,j,k]表示从结点i到结点j的只经过(1..k)集合中的结点的最短路径长度，则
  1.若最短路径经过点ｋ，则D[i,j,k] = D[i,k,k-1] + D[k,j,k-1];
  2.若最短路径不经过点ｋ，则D[i,j,k] = D[i,j,k-1]；
  因此，Ｄ[i,j,k] = min(D[i,j,k-1], D[i,k,k-1] + D[k,j,k-1]);
• 实际操作过程中，我们只需要从(1..n)遍历结点k，不断更新求取每两个结点之间的最短距离即可，最后得到的包含所有结点信息的距离矩阵。

题目描述

本题目描述引自hihocoder第二十四周hihocoder1089。
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，分别表示鬼屋中地点的个数和道路的条数。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^2，M<=10^3, 1 <= length_i <= 10^3。
对于100%的数据，满足迷宫中任意两个地点都可以互相到达。
【输出】
对于每组测试数据，输出一个N*N的矩阵A，其中第i行第j列表示，从第i个地点到达第j个地点的最短路径的长度，当i=j时这个距离应当为0。
【样例输入】

5 12
1 2 967
2 3 900
3 4 771
4 5 196
2 4 788
3 1 637
1 4 883
2 4 82
5 2 647
1 4 198
2 4 181
5 2 665

【样例输出】

0 280 637 198 394 
280 0 853 82 278 
637 853 0 771 967 
198 82 771 0 196 
394 278 967 196 0 

代码实现

#include <iostream>
#include <string.h>
#define N 105
using namespace std;

unsigned len[N][N];

int main()
{
    int n, m;
    int from, to;
    unsigned length;
    memset(len, -1, sizeof(len));
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        len[i][i] = 0;
    for(int i = 1; i <= m; ++i)
    {
        cin >> from >> to >> length;
        len[from][to] = len[to][from] = min(length, len[from][to]);
    }
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(len[i][k] != (unsigned)-1 && len[k][j] != (unsigned)-1)
                {
                    len[i][j] = len[j][i] = min(len[i][j], len[i][k] + len[k][j]);
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            cout << len[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

SPFA算法

SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，通过添加一个队列对Bellman-Ford算法进行优化。

算法思想

• 设立一个先进先出的队列用于保存待优化的结点；
• 每次取出队首结点进行计算，使用队首结点的最短路径估计值对其他结点进行松弛操作，并将进行了松弛的结点放入队列中；

算法描述

本算法描述引自hihocoder第二十五周hiho1093。
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^5，M<=10^6, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
对于100%的数据，满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
【输出】
对于每组测试数据，输出一个整数Ans，表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。
【样例输入】

5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63

【样例输出】

172

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define N 100010
using namespace std;
vector<pair<int, int> > len[N];
bool source[N] = {false};//判定结点是否已经在队列中
unsigned state[N];//s源节点到各节点的距离状态
queue<int> que;
int main()
{
    memset(state, -1, sizeof(state));
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    int from, to, length;
    while(m--)
    {
        cin >> from >> to >> length;
        len[from].push_back(make_pair(to, length));
        len[to].push_back(make_pair(from, length));
    }
    state[s] = 0;
    que.push(s);
    while(!que.empty())
    {
        for(const auto x : len[que.front()])
        {
            if(state[que.front()] != (unsigned)-1)
            {
                if(state[que.front()] + x.second < state[x.first])
                {
                    state[x.first] = state[que.front()] + x.second;
                    if(source[x.first])
                    {
                        continue;
                    }
                    else
                    {
                        que.push(x.first);
                        source[x.first] = true;
                    }
                }
            }
        }
        source[que.front()] = false;
        que.pop();
    }
    cout << state[t] << endl;
    return 0;
}

总结

• 最短路径算法既是图论的常用算法，同时也在路由算法中有着重要的应用。
• 万变不离其宗的经典算法思想动态规划和贪心算法。