在 R 中使用 C++ Routing 包的 Dijkstra 方法

Question

我想知道如何使用 cppRouting 包使用 dijikstra 方法。我的数据库包含不同位置之间的距离数据，我想用这种方法来解决我的问题，即计算这些位置之间的最短路径。我研究并看到了这个适用于此方法的软件包。

包裹：https://cran.r-project.org/web/packages/cppRouting/cppRouting.pdf

> df <- read_excel('C:/Users/Local.xlsx')
> df
# A tibble: 6 x 6
         `Local 1`      `Loca 2`    `Local 3`     `Local 4`      `Local 5` `Local 6`
          <dbl>         <dbl>         <dbl>         <dbl>         <dbl>         <dbl>
1            0           350.         1279.         1544.         2393.         2837.
2          350.            0          1365.         1807.         2605.         3159.
3         1279.         1365.            0           946.         1386.         2433.
4         1544.         1807.          946.            0           918.         1502.
5         2393.         2605.         1386.          918.            0          1483.
6         2837.         3159.         2433.         1502.         1483.            0

Answer 1

我是 cppRouting 包的作者。计算距离或路径的主要数据是图表，你不提供，你有吗？

我猜你读了一些距离矩阵，但你的输入数据是什么？路网 ?

请阅读 this 了解如何使用 cppRouting 包。

Answer 2

输入数据是一个图表。图是由边连接的一组顶点（或节点）。图形通常用于表示像道路这样的网络，其中边是路段，节点是交叉点。如果每条边都有一个权重，描述距离或行进时间，则该图是加权的。

看这个有向图的简单例子，让我们假设所有边的长度相等：

在 R 和 cppRouting 包中，图形必须是描述每条边的数据框：

library(cppRouting)
library(igraph)

graph<-data.frame(from=c(0,1,2,3,4,2),
                  to=c(1,2,3,0,2,4),
                  weight=c(1,1,1,1,1,1))

#visualize 
test<-graph_from_data_frame(graph,directed = TRUE)
plot(test,edge.arrow.size=0.2)

现在，如果您想知道节点 0 和 3 之间的最短路径：

cpp_graph<-makegraph(graph,directed=TRUE)
get_path_pair(cpp_graph,from="0",to="3")

如果你想知道最短距离:

get_distance_pair(cpp_graph,from="0",to="3")

希望对您有所帮助。

在 R 中使用 C++ Routing 包的 Dijkstra 方法

Djikstra method using cppRouting package in R

r

shortest-path

dijkstra