最短路径之Dijkstra算法
最短路径之Dijkstra算法
最短路径之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
腾讯云开发者
