【算法学习】最短路径问题（一）

最短路径问题

大家好，这里是新来的工人~

是一个没学过太多算法编程内容的rookie

所以文章的问题也不难，欢迎小白们一起来看

语言用的是C++，当然，算法部分比较重要

希望第一篇文章能写好，

让同为小白的读者读懂吧~

话不多说，那就开始本期的内容吧

目录

01 问题介绍

02 深度优先遍历

03 Floyd算法

04 Dijkstra算法

05 Bellman-Ford算法

06 SPFA算法

07 算法总结

01

问题介绍

简单地说，就是给定一组点，给定每个点间的距离，求出点之间的最短路径。举个例子，乘坐地铁时往往有很多线路，连接着不同的城市。每个城市间距离不一样，我们要试图找到这些城市间的最短路线。

路径问题大概有以下几种：

• 确定起点的最短路径问题：已知起始点，求起点到其他任意点最短路径的问题。即单源最短路径问题。
  
• 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终点，求最短路径的问题。在无向图（即点之间的路径没有方向的区别）中该问题与确定起点的问题完全等同，在有向图（路径间有确定的方向）中该问题等同于把所有路径方向反转的确定起点的问题。
  
• 确定起点终点的最短路径问题：已知起点和终点，求任意两点之间的最短路径。即多源最短路径问题。
  

我们先说明如何输入一个图，并以此为例：

我们通过这样的形式输入数据：
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

其中，第一行表示共有5个点（可以理解为城市），8条边（理解为路）。

注意，这里一行的三个数据分别表示i点，j点，和从i到j的单向距离！单向！单向！

我们直接输出最短路程。（也可以加上标记输出路径）

在具体解决问题之前，我们先要把这些数据存储起来，方便调用。

这里我们直接用一个二维数组来模拟这个图（它的名字叫邻接矩阵）：

∞表示到达不了。

在图中，第i列第j行表示的是i到j的距离。其中，将到自己的距离定义为0，用无穷定义没有路径连通。存储到数组中，可以通过二维数组表示。

下面我们就开始分别讲解几种解决最短路径问题的经典算法。

02

深度优先遍历（DFS）

我们知道，深度优先搜索常用于走迷宫，是一种遍历全图的暴力方法。同理，我们利用深度优先遍历，也是通过暴力遍历全图的方法来找到最短路径。

因为我们可以在输入数据是对城市进行编号，所以我们将问题的描述改为求从1号城市到5号城市的最短路径长度 。（即初始城市到最后的城市）

我们通过DFS递归函数，从起始1号城市起，不断地判断是否可以通过一个城市到达最后的5号城市（在回溯中判断），然后记录最小路程，不断更新。

关于深度优先搜索的知识在此就不细讲了，有兴趣的朋友可以自行搜索。

这里直接附上C++的代码，讲解见注释。

//DFS解最短路径问题 
#include <iostream>
using namespace std;
const int INF=99999999;//正无穷
int minn=INF;
int n,dist[105][105],book[105];
void dfs(int cur,int dis)
{
    int j;
    //一点点优化：如果本次查找的路径到此已经超过前面查找的最短路径总长，就不需要再继续了
    if(dis>minn)
        return;
    if(cur==n)//到达要查的城市 
    {
        minn=min(dis,minn);
        return;
    }
    for(j=1;j<=n;j++)//从1号城市到n号城市依次尝试看是否能通过j到达n 
    {
        if(dist[cur][j]!=INF&&book[j]==0)//判断当前城市cur到城市j是否有路，并判断城市j是否已经走过
        {
            book[j]=1;//标记已经走过
            dfs(j,dis+dist[cur][j]);//从城市j再出发，继续寻找
            book[j]=0;
        }
    }
    return;
}
int main()
{
    int i,j,m,a,b,c;
    cin>>n>>m;
    //初始化二维矩阵
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j)    dist[i][j]=0;   //到自己的距离为0
                else    dist[i][j]=INF;  //距离为无限，默认到不了 
            //读入城市之间的距离
            for(i=1;i<=m;i++)
            {
                cin>>a>>b>>c;
                dist[a][b]=c;
            }
            //从1号城市出发,接下来就交给函数dfs了~ 
            book[1]=1;
            dfs(1,0);
            cout<<minn;
        return 0;
}

可能有人会问，深度优先搜索的兄弟广度优先搜索算法呢？事实上，基于广度优先遍历依照节点到初始点的节点数遍历全图的特点，它能解决没有权值（也就是默认每条路程一样长）的图的最小路径问题，但对有权值的图，BFS很难解决（即使加上minn指标，我们也无法处理“回头”的路径）。我们就不在此讲解了。

贴上运行结果：