最短路径问题

发表于

1.最短路径算法介绍

问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

解决问题的算法：

  • Floyd算法
  • Dijkstra算法
  • SPFA算法

2.Floyd算法

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

假设图中顶点个数为N，则需要对二维数组a进行N次更新。更新前，a[i][j]代表从顶点i到顶点j的距离，如果i和j不相邻则a[i][j]=∞，顶点b[i][j]则为j的值。接下来对数组a进行N次更新。第一次更新时，取第一个点为中介点，则i——①——j的距离可以表示为a[i][1]+a[1][j],
如果这个值小于a[i][j]，就把a[i][j]的值更新为a[i][1]+a[1][j]，
。同理，第k次更新时，如果 a[i][j] > a[i][k]+a[k][j] ，就更新a[i][j]=a[i][k]+a[k][j]

  • 贴个代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    #include <iostream>
    #include <cstring>
    #define N 999999
    using namespace std;
    int main()
    {
        int n,m;
        int point1,point2,dis;
        int a[100][100];
        memset(a,N,sizeof(a));
        cin>>n>>m; //n 顶点个数，m 边数
        for(int i=1;i<=n;i++)
            a[i][i]=0;

        for(int i=1;i<=m;i++)
        {
            cin>>point1>>point2>>dis;
            a[point1][point2]=dis;
        }

        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(a[i][j]>a[i][k]+a[k][j])
                        a[i][j]=a[i][k]+a[k][j];

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                cout<<a[i][j]<<' ';
            cout<<endl;
        }

        return 0;
    }

3.Dijkstra算法

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单元最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点。
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
（不会贴图 先不贴了

  • 下面是代码 （算法部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    void Dijk()//我们这里起点为1号编码点。我们这里的d[]表示从起点到这个点需要的权值。w[a][b]表示点a到点b这条边的权值.
    {
        int  v, tmp;
        memset(vis, 0, sizeof(vis));
        for (int i=1; i<=n; i++)
            d[i] = w[1][i];//对于起点的初始化
        d[1] = 0;
        vis[1] = 1;
        for (int i=1; i<=n; i++)//控制连接点的次数，例如上图，九个点，就循环九次。
        {
            tmp = N;//这里N表示无穷大。
            for (int j=1; j<=n; j++)
            {
                if (tmp>d[j] && !vis[j])
                {
                    tmp = d[j];
                    v = j;
                }
            }//每次我们都找到距离起点最近的点v
            vis[v] = 1;
            for (int k=1; k<=n; k++)
            {
                if(!vis[k])
                    d[k]=min(d[k],d[v]+w[v][k]);
            }
        }
    }

3.SPFA算法

SPFA算法是求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。

我们用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止
我们要知道带有负环的图是没有最短路径的，所以我们在执行算法的时候，要判断图是否带有负环，方法有两种：

  1. 开始算法前，调用拓扑排序进行判断（较为费时）
  2. 如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）

(还没学完，学完再补坑

Donate comment here