欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迪杰特斯拉算法伪码

程序员文章站 2022-05-22 10:49:49
...

Dijkstra算法有两个核心要点:A、从1为中心出发,B、分为两个集合

求1-->n的最小距离

辅助数据

N : 所有点集合

S : 已计算距离点的集合

M[i][j]: i-->j的距离值,-1表示不可达

D[]:距离数组

D[1] =0,D[i] = +inf,{i!=0}
S= {1}
Count = N
While(--Count>0){
      min = +inf
      idx = 0 
      for s in S {
           for i in (N-S) {
              if M[s][i] !=-1 && min < (M[s][i] + D[s]) {
                   min = (M[s][i]+D[i])
                   idx = i
               }
           }
       if idx !=0{
            add idx in S
            D[idx] = min
       }else{
            S and N-S is not available
            break
      }
}
// 时间复杂度为n^3

不断地更新D,不采用笛卡尔积,复杂度下降为n^2,经典的m*n变为了m+n

D[1] =0,D[i] = +inf,{i!=0}
S= {1}
Count = N
While(--Count>0){
      min = +inf
      idx = 0 
      for i in (N-S) {
          if  D[i] < min {
                idx = i
               }
      }
      if idx !=0{
            add idx in S
            D[idx] = min
            
           for i in (N-S) {
               if D[i] > D[idx] + M[idx][i] {
                   D[i] = D[idx] + M[idx][i] 
               }
            }               
       }else{
            S and N-S is not available
            break
      }
}