CSP-S 题库Dijkstra 算法程序完善题

补全以下 Dijkstra 单源最短路的核心框架(填空处用 __ 表示):

程序完善题 第 50 题 · CSP-S 提高级 初赛题库
dis[__]=0;                 // 源点距离初始化
for(int i=1;i<=n;i++){
    int u=-1, best=INF;
    for(int j=1;j<=n;j++)
        if(!vis[j] && dis[j]<best){ best=dis[j]; u=j; }
    if(u==-1) break;
    __=1;                  // 标记 u 已确定最短路
    for(每条边 u->v)
        if(!vis[v] && dis[u]+w < dis[v]) dis[v]=dis[u]+w;
}
  • 第 1 空(源点距离初始化)应填什么?
    答案:s(即 dis[s]=0)
    解析:源点到自身距离为 0。
  • 第 2 空(标记已确定)应填什么?
    答案:vis[u]=1
    解析:每次选出未确定中距离最小的 u,标记为已访问(已确定最短路)。

本题收录于「CSP-S 提高级 初赛题库」,共 51 道题,全部提供答案与解析。可进入在线练习系统按知识点随机组卷、自动批改并归集错题。

进入在线练习 查看完整试卷 本类全部题目