• Posts tagged "最短路径"

Blog Archives

知识图谱:最短路径算法Bellman-Ford

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像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算法。

目录

  1. Bellman-Ford算法介绍
  2. R语言调用Bellman-Ford算法
  3. 自己手写Bellman-Ford算法
  4. 算一个复杂点的网络关系图

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

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹, 分析师/程序员/Quant: R,Java,Nodejs
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/r-graph-shortest-path-dijkstra/

前言

最短路径是图算法中的基本算法,被普遍应用于多种场景中,比如在实际生活中的路径规划、地图导航,建立道路交通网、物流运输网络、计算机网络等,这时就可以使用最短路径算法。

常用的最短路径算法包括:Dijkstra算法,A star算法,Bellman-Ford算法,SPFA算法(Bellman-Ford算法的改进版本),Floyd-Warshall算法,Johnson算法以及Bi-direction BFS算法。

目录

  1. 最短路径算法介绍
  2. Dijkstra 算法原理
  3. 用R语言调用 Dijkstra 算法

1. 最短路径算法介绍

最短路径问题是图论研究中一个经典算法问题,旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同,算法的具体形式包括:

  • 确定起点的最短路径问题,即给定起始节点,求该节点到其他剩余节点的最短路径,适合使用Dijkstra算法
  • 确定终点的最短路径问题,即给定终点,求其他节点到该终点的最短路径。在无向图中,该问题与确定起点的问题等价;在有向图中,问题等价于把所有路径方向反转的确定起点的问题;
  • 确定起点终点的最短路径问题,即给定起点和终点,求两节点之间的最短路径;
  • 全局最短路径问题,即求图中所有节点之间的最短路径,适合使用Floyd-Warshall算法。

多种最短路径算法

最短路径算法 描 述
迪杰斯特拉算法
Dijkstra
寻找某个特定顶点到其它所有顶点的最短路径,该算法要求所有路径的权值为非负数。
贝尔曼福特算法
Bellman-Ford
寻找某个特定顶点到其它所有顶点的最短路径,该算法允许路径的权值为负数。
弗洛伊德算法
(Floyd-Warshall)
寻找各个顶点之间的最短路径,允许非环路的路径权值为负数,该算法不仅适用于稀疏图,在稠密图(路径数量多的图)中寻找最短路径的效率也很高。
约翰逊算法
(Johnson)
寻找各个顶点之间的最短路径,允许非环路的路径权值为负数,该算法更适用于稀疏图(路径数量少的图)。

2. Dijkstra 算法原理

Dijkstra算法,于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出,用于解决赋权有向图的单源最短路径问题。所谓单源最短路径问题是指确定起点,寻找该节点到图中任意节点的最短路径,算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。

基本思想

  1. 通过Dijkstra计算图中的最短路径时,需要指定一个起点A。
  2. 简历两个数组S和U,S用于记录已求出最短路径的顶点(以及相应的最短路径长度),U用于记录还未求出最短路径的顶点(以及该顶点到起点A的距离)。
  3. 初始时,数组S中只有起点A;数组U中是除起点A之外的顶点,并且数组U中记录各顶点到起点A的距离。如果顶点与起点A不相邻,距离为无穷大INF。
  4. 从数组U中找出路径最短的点X,并将其加入到数组S中;同时,从数组U中移除顶点X。接着,更新数组U中的各顶点到起点A的距离。
  5. 重复第4步操作,直到遍历完所有顶点。

下面,我们来举例说明一下算法,创建一个带权重的有向图,来描述对最短路径。

开始点为A,数组U为开始列,数组S为上层节点列。通过6次遍历,找到从A到G的最短路径。

3. 用R语言调用 Dijkstra 算法

我们用R语言中,igraph包已经实现了Dijkstra算法,我们可以直接调用igraph包的shortest.pahs()函数进行最短路径的计算。首先,安装和加载 igraph 程序包

> install.pacakges("igraph")
> library(igraph)

生一个有向有权重的网络图,如上例所示。

> df<-data.frame(
+   from=c("A","A","A","B","D","B","C","D","C","F","E","F"),
+   to=c("B","D","C","C","C","E","E","F","F","E","G","G"),
+   weight=c(4,6,6,1,2,7,6,5,4,1,6,8)
+ )
> df
   from to weight
1     A  B      4
2     A  D      6
3     A  C      6
4     B  C      1
5     D  C      2
6     B  E      7
7     C  E      6
8     D  F      5
9     C  F      4
10    F  E      1
11    E  G      6
12    F  G      8

把数据生成igraph图对象,再以网络图进行展示。

# 生成igraph对象
> a<-graph_from_data_frame(df, directed = TRUE, vertices = NULL)

# 画图
> E(a)$arrow.size<-1
> E(a)$arrow.width<-0.2
> E(a)$label<-df$weight
> plot(a)

上面我们把节点涂色了,下面继续把边也涂色。首先,找到最短路径上的边,把最短路径边涂红色,非最短路径的边涂灰色。

# 通过最短路径的节点,建立边的关系
> s_vert<-data.frame(from=s_node[-length(s_node)],to=s_node[-1])

# 找到网络图中所有的边
> a_vert<-as_data_frame(a,what="edges")

# 找到最短路径的边的索引
> idx<-which(paste0(a_vert$from,"-",a_vert$to) %in% paste0(s_vert$from,"-",s_vert$to))
> idx
[1]  1  4  9 10 11

# 涂色:红色为最短路径的边,灰色为非最短路径的边
> a_vert$color<-"gray"
> a_vert$color[idx]<-"red"

# 画图
> E(a)$color<-a_vert$color
> plot(a)

用Dijkstra算法,计算从A开始,到B,C,D,E,F,G的所有节点的最短距离。

> shortest.paths(a,"A", algorithm = "dijkstra")
  A B D C F  E  G
A 0 4 6 5 9 10 16

输出结果,从A到B最短距离为4,从A到D最短距离为6,从A到C最短距离为5,从A到F最短距离为9,从A到E最短距离为10,从A到G最短距离为16。

当然,我们除了想知道最短距离,还想知道最短距离的路径是什么样的。接下来,我们先计算最短距离路径上的点,并发点进行涂色。

# 计算最短距离经过的点
> s_node<-all_shortest_paths(a,"A","G")$res[[1]]$name
> snode
[1] "A" "B" "C" "F" "E" "G"

# 把节点进行涂色
> cols<-data.frame(label=V(a)$name,color=0)
> cols$color[which(cols$label %in% s_node)]<-1
> cols
  label color
1     A     1
2     B     1
3     D     0
4     C     1
5     F     1
6     E     1
7     G     1

# 画图
> V(a)$color<-cols$color
> plot(a)

其中,黄色点为最短距离穿过的节点,白色节点为不在最短距离路径上的节点。

上面我们把点进行了涂色,下面我们继续边最少路径的边进行涂色。首先,根据最短路径的节点,创建边的关系。然后对边进行涂色,在最短路径的边涂为红色,不在最短路径的边涂为灰色。

# 建立最短路径节点的关系
> s_vert<-data.frame(from=s_node[-length(s_node)],to=s_node[-1])

# 找到网络图的完整路径
> a_vert<-as_data_frame(a,what="edges")

# 找到最短路径的边的索引
> idx<-which(paste0(a_vert$from,"-",a_vert$to) %in% paste0(s_vert$from,"-",s_vert$to))
> idx
[1]  1  4  9 10 11

# 涂色
> a_vert$color<-"gray"
> a_vert$color[idx]<-"red"

# 画图
> E(a)$color<-a_vert$color
> plot(a)

这样就在完整的网络图中,可以从开始节点A,按红色路径走到G,生成了最短路径所过过的节点和边了。

扩展一下,我们用Dijkstra算法,分别计算从不同点开始,到所有不同的点的最短距离,通过矩阵来表达,任意2个节点的最短距离。

> shortest.paths(a, algorithm = "dijkstra")
   A  B  D  C F  E  G
A  0  4  6  5 9 10 16
B  4  0  3  1 5  6 12
D  6  3  0  2 5  6 12
C  5  1  2  0 4  5 11
F  9  5  5  4 0  1  7
E 10  6  6  5 1  0  6
G 16 12 12 11 7  6  0

通过上面的步骤,我们就实现了在R语言中使用Dijkstra算法,计算的最短路径算法。本来还想着,自己再来实现一遍,发现网上有很多的开源的代码,还让自己休息一下吧。下篇文章将介绍,知识图谱:最短路径算法Bellman-Ford算法,应该是需求自己手写了。

本文算法代码已上传到github: https://github.com/bsspirit/graph/blob/main/dijkstra.r

转载请注明出处:
http://blog.fens.me/r-graph-shortest-path-dijkstra/
打赏作者