图论最短路径算法——Dijkstra

时间：2021-10-13 15:12:19

说实在的，这算法很简单，很简单，很简单……因为它是贪心的，而且码量也小，常数比起SPFA也小。

主要思想

先初始化，dis[起点]=0，其它皆为无限大。

还要有一个bz数组，bz[i]表示i是否确定为最短路径

for i=1 to n

{

    在未确定最短路径的点中找出u使dis[u]最小

    bz[u]=1;

    更新与u相连的所有点

}

就这么简单。

实现讲解

其实也很好实现。可以用邻接表储存，也可以用邻接矩阵储存，虽然会慢一点。因为Dijkstra算法本就是对付稠密图的，不过我还是建议用邻接表，见SPFA实现讲解

注意事项

Dijkstra不能处理负边权的状况，所以要看清题目大意才用它哦！

具体代码

#include <iostream>

#include <algorithm>

#include <string.h>

#include <math.h>

#include <limits.h>

using namespace std;

struct _Way//定义_Way类型，表示某点到点y的距离为len

{

    int y,len;

};

int n,m;

int q;

_Way way[1001][1001] {};//way[i][j]表示从i开始的第j条路

_Way* bz[1001][1001] {};//读入时标记，防止重边出现。bz[i][j]指向从i到j的直接路径

int now[1001] {};//now[i]表示从i开始的边的数量

int dis[1001] {};//dis[i]表示从起点到i的最短路径

int min(int a,int b){return a<b?a:b;}

void Dijkstra(int);

int main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

    for(int i=1;i<=m;i++)

    {

        int x,y,len;

        cin>>x>>y>>len;

        if (bz[x][y]!=NULL)//若重边则替换之

        {

            bz[x][y]->len=min(bz[x][y]->len,len);

            continue;

        }

        now[x]++;

        way[x][now[x]].y=y;

        way[x][now[x]].len=len;

        bz[x][y]=&(way[x][now[x]]);//标记好地址

    }

    cin>>q;

    Dijkstra(q);

    for(int i=1;i<=n;i++)

    {

        if (dis[i]!=INT_MAX)

            cout<<dis[i]<<endl;

        else

            cout<<"-1"<<endl;

    }

    return 0;

}

void Dijkstra(int q)//注意Dijkstra算法不能有负边权

{

    bool bz[1001] {};//bz[i]表示点i是否已标记成最短路径

    for(int i=0;i<=n;i++)

        dis[i]=INT_MAX;

    dis[q]=0;//初始化

    for(int i=1;i<=n;i++)

    {

        int u {};

        for(int j=1;j<=n;j++)

            if ((!bz[j])&&(dis[j]<dis[u]))

                u=j;//u为未确定点中dis最小的点

        if (u==0) break;

        bz[u]=1;//标记为确定点

        for(int i=1;i<=now[u];i++)

            dis[way[u][i].y]=min(dis[way[u][i].y],dis[u]+way[u][i].len);//更新与其相连的所有点

    }

}

优化

用堆优化，暂时不会。

SPFA和Dijkstra哪个强？

SPFA擅长于稀疏图，而Dijkstra擅长于稠密图

SPFA可以处理负边权，Dijkstra不可以处理负边权

SPFA时间复杂度为O(kE)，Dijkstra时间复杂度为O(n^2)

SPFA的空间要比Dijkstra多一个队列

SPFA的优化有SLF和LLL，Dijkstra的优化有堆优化

SPFA和Dijkstra均不可以处理负权回路

SPFA的时间系数要比Dijkstra大（Floyed和Ford笑了）

SPFA和Dijkstra都是单源的（Floyed又笑了）

没有边的图 O(1)特殊判断 SPFA秒过，完全图Dijkstra秒过（Floyed和Ford骄傲地说：“我们的时间是固定的！”）

相关文章