算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。
算法为王的时代正式到来….
关于作者:
- 张丹, 分析师/程序员/Quant: R,Java,Nodejs
- blog: http://blog.fens.me
- email: bsspirit@gmail.com
转载请注明出处:
http://blog.fens.me/r-graph-shortest-path-bellman-ford/
前言
最短路径是图算法中的基本算法,被普遍应用于多种场景中,如企业生产经营的场景中,现金流的生产和交换的过程,会产生正向的现金流比如经营收入所得,也会产生负向的现金流比如借款、支出等。如果我们以企业作为节点,以现金流做为边时,由于出现了负向的现金流的边,这样构成负权重的网络图谱,就需要用Bellman-Ford算法来实现。
常用的最短路径算法包括:Dijkstra算法,A star算法,Bellman-Ford算法,SPFA算法(Bellman-Ford算法的改进版本),Floyd-Warshall算法,Johnson算法以及Bi-direction BFS算法。
目录
- Bellman-Ford算法介绍
- R语言调用Bellman-Ford算法
- 自己手写Bellman-Ford算法
- 算一个复杂点的网络关系图
1. Bellman-Ford算法介绍
Bellman Ford算法最初于1955年被Alfonso Shimbel提出,但最终基于1958和1956年发表论文的 Richard Bellman和Lester Ford, Jr.二人命名。Edward F. Moore于1957年也提出了该算法,因此该算法有时也称作是Bellman Ford Moore算法。
Bellman-Ford算法与Dijkstra算法一样,解决的是单源最短路径问题。两者不同之处在于,Dijkstra只适用于无负权边的图,而Bellman-Ford算法无此限制:无论是否有向,无论是否有负权边,只要图中没有负权环,则该算法可以正确地给出起点到其余各点的最短路径,否则报告负权环的存在。
Bellman-Ford 算法采用动态规划进行设计,实现的时间复杂度为 O(V*E),其中 V 为顶点数量,E 为边的数量。每次松弛操作实际上是对相邻节点的访问(相当于广度优先搜索),第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过|V| – 1条边,所以可知贝尔曼-福特算法所得为最短路径,也可只时间复杂度为O(VE)。
Bellman-Ford 算法描述:
- 创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,初始均为 Infinite,源顶点距离为 0;
- 计算最短路径,执行 V – 1 次遍历;
- 对于图中的每条边:如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d,则更新终点 v 的距离值 d;
- 检测图中是否有负权边形成了环,遍历图中的所有边,计算 u 至 v 的距离,如果对于 v 存在更小的距离,则说明存在环;
下面,我们来举例说明一下算法,创建一个带负权重的有向图,来描述对最短路径
开始点为A,数组U为开始列,数组S为上层节点列。通过6次遍历,找到从A到G的最短路径。
通过4次遍历,其实就能获得从A到D的最短路径。
2. R语言调用Bellman-Ford算法
接下来,我们可以继续使用R语言的igraph包来进行实现。新建数据集,如上面例子所示。
# 加载igraph库
> library(igraph)
# 新建图数据
> df<-data.frame(
+ from=c("A","A","B","B","B","D","D","E"),
+ to=c("B","C","C","D","E","B","C","D"),
+ weight=c(-1,4,3,2,2,1,5,-3)
+ )
# 用igraph画图
> a<-graph_from_data_frame(df, directed = TRUE)
> E(a)$arrow.size<-1
> E(a)$arrow.width<-0.2
> E(a)$label<-df$weight
# layout需要设置一下,不然图的展示会很不好看
> plot(a,layout=layout.gem)
layout需要设置一下,不然图的展示会节点叠加在一起,就看不出来图的样子了,我这里选择layout.gem类型。
然后,使用shortest.paths()函数,进行bellman-ford算法计算最短路径的时候,就报错了。错误提示,图形成负权重的环路。
# 使用bellman-ford算法
> shortest.paths(a,"A", algorithm = "bellman-ford")
Error in shortest.paths(a, "A", algorithm = "bellman-ford") :
At core/paths/bellman_ford.c:157 : cannot run Bellman-Ford algorithm, Negative loop detected while calculating shortest paths
尝试了多种数据集,只要是有负值shortest.paths()函数都会报错,无论是否有负权重的环路,我也尝试找了几个的其他的R包,竟然没有发现Bellman-Ford算法的实现,因此只好自己手动写一个了。
3. 自已手写Bellman-Ford算法
于是,我就自己实现bellman-ford算法函数。写了2个小时,好像不练习了,可能还是会有bug吧。
在实现过程中,我们没有做“环”的判断,可能会导致计算逻辑出现问题。我假设了节点的寻路的过程是排序好的,不会出现对于一节点的反复寻路,当然这个假设条件,在某些复杂的场景中是不靠谱的,所以大家在使用的我的代码的时候,当一个基本版参考和学习用,不要直接用于自己的生产环境。
# bellman-ford 最短距离算法
# @param df数据集
# @param start开始节点
bellman_ford<-function(df,start="A"){
# 初始化结果数据集
rs<-data.frame(from=start,to=start,weight=0)
# 初始化结束节点
finishnode<-c()
# 初始化开始节点
nodes<-rs
# 当开始节点数量<结束节点数量时,继续循环计算
while(length(finishnode)<length(rs$to)){
# 过滤已计算过的结束节点
if(length(finishnode)>0){
nodes<-rs[-which(rs$to %in% finishnode),]
}
# 对原始数据进行循环,遍历每一行
for(i in 1:nrow(df)){
row<-df[i,];row
# 对结束节点进行循环,遍历每一个结束节点
for(j in nodes$to){
if(row$from==j){
# 把之前结束节点的权重叠加本次计算中
row$weight<-row$weight+rs$weight[which(rs$to==j)]
# 把结束节点加入到结果数据集
rs<-rbind(rs,row)
}
}
}
# 保留最短的唯一结束节点
rs2<-rs[order(rs$weight),]
n<-which(duplicated(rs2$to))
if(length(n)<0){
rs2<-rs2[-n,]
rs<-rs2[order(as.numeric(row.names(rs2))),]
}
# 更新已经完成的结束节点
finishnode<-c(finishnode,nodes$to)
}
return(rs)
}
执行计算,计算A点其他所有节点的距离。
> rs<-bellman_ford(df,"A")
> rs
from to weight
1 A A 0
2 A B -1
3 B C 2
5 B E 1
8 E D -2
结果数据集中,to 表示从开始点A到节点的距离,每一行from 到 to 表示,最短路径的顺序。
# 计算2点间的最短路径
# @param rs 结果数据集
# @param start 开始节点
# @param end 结束节点
get_shortest_path<-function(rs,start,end){
# 初始化节点
q<-c(start)
idx<-which(rs$from==start)
# 判断有几个分支
if(length(idx)>0){
for(i in idx){
# 递归计算
q2<-get_shortest_path(rs,rs$to[i],end)
if(tail(q2,1)==end){
q<-c(q,q2)
}
}
}
# 查看队列状态
# print(q)
# 当找到结束节点,程序停止
if(tail(q,1)==end){
return(q)
}
return(q)
}
# 计算从开始节点到结束节点的路径
> path<-get_shortest_path(rs[-1,],"A","D")
> path
[1] "A" "B" "E" "D"
最后,我们把从A点到D的最短路径涂上颜色,来出来。
# 把路径合并成data.frame
> path2<-data.frame(from=path[-length(path)],to=path[-1])
# 找到最短路径的索引
> idx<-which(paste0(df$from,"-",df$to) %in% paste0(path2$from,"-",path2$to))
# 涂色
> df$color<-"gray"
> df$color[idx]<-"red"
> E(a)$color<-df$color
> plot(a,layout=layout.gem)
红色路径就表示从A到D点的最短路径,看上去结果也是对的。在实现过程中,我们没有做“环”的判断,可能会导致计算逻辑出现问题。自己用写了一段算法,用R语言写算法,感觉比起C或者JAVA还要是简单很多的,因为大量基础函数提供了很多的功能和数据结构支持,不用像底层语言什么结构都需要自己从头写起。
4. 算一个复杂点的网路关系图
生成新数据集,共11个节点。
> df2<-data.frame(
+ from=c("A","B","C","D","C","F","B","B","F","G","H","F","E"),
+ to= c("B","C","D","C","E","E","F","G","G","H","I","I","J"),
+ weight=c(5,20,10,-5,75,25,30,60,5,-50,-10,50,100)
+ )
用igraph进行画图展示。
> a2<-graph_from_data_frame(df2, directed = TRUE)
> E(a2)$arrow.size<-1
> E(a2)$arrow.width<-0.2
> E(a2)$label<-df2$weight
> plot(a2,layout=layout.gem)
计算A开始到所有节点的最短路径。
> rs<-bellman_ford(df2,"A")
> rs
from to weight
1 A A 0
2 A B 5
3 C D 35
6 F E 60
7 B F 35
9 F G 40
10 G H -10
11 H I -20
13 E J 160
21 B C 25
计算A到D的最短路径路线,并画科展示。
# 计算 A 到 D的最短路径
> path<-get_shortest_path(rs[-1,],"A","D")
> path
[1] "A" "B" "C" "D"
# 画图
> path2<-data.frame(from=path[-length(path)],to=path[-1])
> idx<-which(paste0(df2$from,"-",df2$to) %in% paste0(path2$from,"-",path2$to))
> df2$color<-"gray"
> df2$color[idx]<-"red"
> E(a2)$arrow.size<-1
> E(a2)$arrow.width<-0.2
> E(a2)$color<-df2$color
> plot(a2,layout=layout.gem)
计算A到I的最短路径路线,并画科展示。
# 计算 A 到 I的最短路径
> path<-get_shortest_path(rs[-1,],"A","I")
> path
[1] "A" "B" "F" "G" "H" "I"
# 画图
> path2<-data.frame(from=path[-length(path)],to=path[-1])
> idx<-which(paste0(df2$from,"-",df2$to) %in% paste0(path2$from,"-",path2$to))
> df2$color<-"gray"
> df2$color[idx]<-"red"
> E(a2)$arrow.size<-1
> E(a2)$arrow.width<-0.2
> E(a2)$color<-df2$color
> plot(a2,layout=layout.gem)
算法和数据结构还是很重要的,图论算法原来仅在计算领域有应用,随着知识图谱的应用普及,相信未来会有更广阔的应用前景,把原来藏在背后的知识,扩展到前台形成新的模型思路。
努力吧,曾经的少年。
本文算法代码已上传到github: https://github.com/bsspirit/graph/blob/main/Bellman-Ford.r
转载请注明出处:
http://blog.fens.me/r-graph-shortest-path-bellman-ford/
[…] 常用的最短路径算法包括:Dijkstra算法,A star算法,Bellman-Ford算法,SPFA算法(Bellman-Ford算法的改进版本),Floyd-Warshall算法,Johnson算法以及Bi-direction BFS算法。 […]