最短路径之Dijkstra算法

最近使用最短路径算法，便将经典的最短路径算法梳理了一下。本文整理最短路径之Dijkstra（迪杰斯特拉）算法。

因为最近在用R语言，所以代码使用R语言完成。语言只是工具，算法才是灵魂。Floyd算法简单暴力，三个for循环搞定。但是相应是要付出代价的，时间复杂度为O(n^3)。今天学习的是一个O(n^2)的算法--经典Dijkstra（迪杰斯特拉）算法，这也是经典贪心算法的好例子。

Dijkstra算法是一种典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。其主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

注意：该算法要求图中不存在负权边。

问题描述：

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

算法描述：

算法思想：

设G=(V,E)是一个带权（或者不加权）有向图（或者无向图），把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

动态执行过程：

算法示例：

给定无向图：

以A为源节点，执行过程如下：

R语言代码：

# R语言经典代码
calDijkstraClassical = function(A, source, mpath = FALSE) {
  ##  输入:  
  ##      A: 邻接矩阵（加权或不加权）  
  ##      source: 源节点-1,2,3......N  
  ##      mpath: 最短路径为多条时，输出多条（TRUE）  
  ##  输出:  
  ## dis: 源节点到其他节点的最短路径距离  
  ## path: 如果 mpath=true, N个list, N个节点的最短路径,矩阵：n个节点的最短路径（每个一条）  
  ## 初始化临街矩阵，不可达置为Inf  
  temp.A<-A  
  temp.A[which(temp.A == 0)] <- Inf  
  #对角线置为0 去自连接  
  diag(temp.A)<-0  
  #节点总数n  
  n <- dim(temp.A)[1]  
  # 记录源节点到其他节点的距离,默认取邻居节点距离 一行n列  
  result.dis <- matrix(0, n, 1)  
  result.dis <- t(temp.A[source, ])  
  # open: OPEN集合即T=V-S，待遍历的节点，初始值为除了source节点之外的节点  
  # close：CLOSE集合即S，存储已访问过的节点，即已求出最短路径的集合 ，初始值为source节点  
  if (source == 1) {    
    open = (source + 1):n  
  } else if (source == n) {    
    open = 1:(source - 1)  
  } else {    
    open = c(1:(source - 1), (source + 1):n)  
  }  
  close<-c(source)  
  # 最短路径存储  
  path = matrix(0,n, n)  
  #  路径第一个节点为初始节点  
  path[, 1] <- source  
  # 如果计算多条最短路径  
  if (mpath) {    
    # 初始化最短路径初始节点为source节点    
    p1 = matrix(c(source, rep(0, n - 1)), , n)    
    # 路径列表    
    result.path = c()    
    for (i in 1:n) {      
      result.path[[i]] = p1    
    }  
  } else {    
    # 只保留一条最短路径    
    path = matrix(0, n, n)    
    path[, 1] = source  
  }  
  # 终止条件open集合为空  
  while (length(open) > 0) {    
    #从open（T）集合中选出待遍历节点中路径最短的节点，该节点是open（T）集合中到close(S)集合距离最小的节点 id从open取出然后放入close集合    
    # id = which(result.dis[open] == min(result.dis[open]))[1]    
    # id为最小距离节点的在open表中的下标    
    id = which.min(result.dis[open])    
    # 将id 加入到close  省略    
    # 最小距离节点的下标对应的节点    
    new.id = open[id]    
    if (mpath) {      
      temp.path <- result.path[[new.id]]      
      temp.path <- matrix(temp.path, ,n)      
      nn <- nrow(temp.path)      
      mm <- ncol(temp.path)      
      temp.id.vec <- apply(temp.path, 1, which.min)      
      id.vec = nn * (temp.id.vec - 1) + matrix(1:nn, nn, 1)      
      temp.path[id.vec] = new.id      
      result.path[[new.id]] = temp.path    
    } else {      
      ## new.id节点的最短路径 第一个元素应该为0      
      temp.id = which.min(path[new.id, ])      
      path[new.id, temp.id] = new.id    
    }    
    # 从open表删除当前节点    
    open = open[-id]    
    ## 更新最短路径   
    if (length(open)>0)    {      
      # 更新节点new.id 的邻居节点的距离,update.node待更新节点，即new.id 的邻居节点中可达的节点      
      update.node = open[temp.A[new.id, open] != Inf]      
      if (length(update.node) > 0) {        
        #遍历要更新的节点        
        for (i in 1:length(update.node)) {          
          # source节点到new.id节点距离+new.id和待更新节点距离之和          
          temp.dis = result.dis[new.id] + temp.A[new.id, update.node[i]]          
          # 如果距离之和小于  直接距离source到待更新节点的直接距离          
          if (temp.dis < result.dis[update.node[i]]) {            
            # 更新最短路径距离            
            result.dis[update.node[i]] = temp.dis            
            # 更新最短路径            
            ## path[update.node[i],which.min(path[update.node[i],])[1]]=new.id            
            # 如果保存多路径            
            if (mpath) {              
              result.path[[update.node[i]]] = result.path[[new.id]]           
            } else {              
              path[update.node[i], ] = path[new.id, ]            
            }          
          } else if ((temp.dis == result.dis[update.node[i]]) && mpath) {            
            # 当最短距离与已有最短距离相同时，加入最短路径集合            
            temp.mat = result.path[[update.node[i]]]            
            add.row = result.path[[new.id]]            
            temp.mat = rbind(temp.mat, add.row)            
            result.path[[update.node[i]]] = temp.mat          
          }       
        }     
      }    
    }  
  }  
  if (mpath) {    
    path = result.path  
  }  
  output<-list(dis=result.dis, path=path)  
  return(output)
}  ## end function

参考:

https://www.cnblogs.com/jason2003/p/7222182.html

https://www.cnblogs.com/wuchanming/p/3874789.html

https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

http://blog.sina.com.cn/s/blog_676069b10101k3tp.html