AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

最短路笔记(1)Dijkstra朴素版

作者: 作者的头像   很正常的事情哇 ,  2019-06-03 15:51:29 ,  所有人可见 ,  阅读 2486


17


20

最短路

无标题.png

Dijkstra朴素算法与堆优化算法时间复杂度对比

         稠密图         稀疏图
          m≈n²           m≈n
朴素       n²             n²
堆优化   n² log n       m log n

bellman-ford算法适合:

从起点开始,最多经过k条边,到其他每个点的最短距离。
两重循环:
for(i=0;i<k;i++)//循环边的数量(经过哪些边)
    for(...)//更新每条边

Dijkstra朴素版

①图的存储——邻接矩阵 g[a][b]

②dist[i]:从1号点到i号点的最短路径
算法流程:
初始化:dist[原点]=0,dist[i]=+∞
for(i=0;i<n-1;i++){
    (1)找出剩下点中距离原点最小的点 t
    (2)用t号点更新其他点的距离
}
时间复杂度:O(n²)

无向图->特殊有向图
a——b    a->b
        a<-b

代码如下:

//Dijkstra朴素版 
#include<bits/stdc++.h>
#define N 1000+10
using namespace std;

int n/*点数*/,m /*边数*/;
int g[N][N];//邻接矩阵,存储边 
int dist[N];//存储每条边到原点的距离
bool st[N];//记录当前点是否已被用来更新 

void dijkstra(){
    memset(dist,0x3f,sizeof(dist));//每条边到原点的距离初始化成正无穷
    dist[1]=0;

    for(int i=0;i<n-1;i++){
        //找出剩下点中距离原点最小的点 
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[j]<dist[t]))
                t=j;

        st[t]=true; 
        //从1号点到j号点的距离能否用经过t的一条路径来更新
        //即1->j能否用1->t和t->j路径来更新 
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}

int main(){
    cin>>m>>n;

    memset(g,0x3f,sizeof(g));//邻接矩阵初始化 

    while(m--){//存储每条边 
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);//可能有重边,两点之间只需保留长度最小的边 
    } 

    dijkstra();
    cout<<dist[n];//输出1号点到n号点的最短距离 

    return 0; 
} 

4 评论


用户头像
潘瑞杰   2019-12-18 20:05         踩      回复

为啥外循环是0 ~ n - 1,不是 0 ~ n 呢?

用户头像
jasonlin   2020-04-12 18:24         踩      回复

总共n的点,起点到起点的最短已经确定了,是0.
接下来的目标是确定剩下来n-1个结点的最短路,所以外循环只需要循坏 n -1 次 即【0 ,n - 1 ) 或者[1,n)


用户头像
秦淮岸灯火阑珊   2019-06-03 19:42         踩      回复

%%%大佬

用户头像
很正常的事情哇   2019-06-04 14:50         踩      回复

emmm,还没有整理完。。。还请多多指点!


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息