来自数据框的 Dijkstra 算法的最短路径

Question

我正在尝试使用 Dijkstra 算法找到图形节点之间的最短路径，方法是使用以下文章中包含的代码：

https://www.r-bloggers.com/2020/10/finding-the-shortest-path-with-dijkstras-algorithm/

但是此代码从边缘列表创建图形。相反，我想从这样的数据框创建图表：

actors <- data.frame(name=c("Alice", "Bob", "Cecil", "David",
                            "Esmeralda"))
relations <- data.frame(from=c("Bob", "Cecil", "Cecil", "David",
                               "David", "Esmeralda"),
                        to=c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"),
                        weights=c(4,5,5,2,1,1))
g <- graph_from_data_frame(relations, directed=TRUE, vertices=actors)

我如何修改文章的代码，使代码在从数据帧（而不是边缘列表）开始定义的图形上工作？

我知道 igraph 包中有一些功能可以计算最短路径，但我想尝试在包外编写一些代码。

谢谢！

编辑

这些是我的数据框：

>dput(relations)
structure(list(From = c("France", "Italy", "Malta", "Spain", 
"Germany", "Austria", "Luxembourg", "Luxembourg", "Luxembourg", 
"Greece", "Slovakia", "Belgium", "Luxembourg", "Estonia", "Germany", 
"Netherlands", "Netherlands", "Cyprus", "Greece", "Lithuania", 
"Estonia", "Greece", "Lithuania", "Slovakia", "Netherlands", 
"Luxembourg", "Estonia", "Malta", "Belgium", "Cyprus", "Austria", 
"Estonia", "Austria", "Germany", "Austria", "Netherlands", "Portugal", 
"Portugal", "Estonia", "Italy", "Spain", "Finland", "Belgium", 
"Spain", "Estonia", "Latvia", "Luxembourg", "Luxembourg", "Netherlands", 
"Italy", "Lithuania", "Cyprus", "Ireland", "Luxembourg", "Ireland", 
"Spain", "Belgium", "Latvia", "Netherlands", "Italy", "Slovenia", 
"Netherlands", "Greece", "Spain", "Austria", "Finland", "Malta", 
"Spain", "Austria", "Lithuania", "France", "Portugal", "Cyprus", 
"Finland", "Spain", "Spain", "Belgium", "Germany", "Germany", 
"Greece", "Netherlands", "Luxembourg", "Estonia", "Ireland", 
"Italy", "Portugal", "Greece", "Estonia", "Belgium", "Germany", 
"Slovenia", "Slovakia", "Lithuania", "Slovenia", "Portugal", 
"Portugal", "Slovakia", "France", "Portugal", "Netherlands"), 
    To = c("Slovakia", "Germany", "Portugal", "Austria", "Latvia", 
    "Cyprus", "Portugal", "Greece", "Italy", "Slovenia", "Ireland", 
    "Malta", "Ireland", "Germany", "Cyprus", "Portugal", "Slovenia", 
    "Italy", "Luxembourg", "France", "Slovakia", "Netherlands", 
    "Greece", "France", "Ireland", "Netherlands", "Cyprus", "Germany", 
    "Portugal", "Austria", "Luxembourg", "Austria", "Spain", 
    "Netherlands", "Belgium", "Cyprus", "Cyprus", "Luxembourg", 
    "Finland", "Belgium", "Lithuania", "Austria", "Spain", "Slovenia", 
    "Luxembourg", "Finland", "Slovenia", "Germany", "Austria", 
    "Slovenia", "Slovenia", "Portugal", "Finland", "Lithuania", 
    "Latvia", "France", "Netherlands", "Cyprus", "Spain", "Malta", 
    "France", "Finland", "Belgium", "Latvia", "Slovenia", "Slovenia", 
    "Cyprus", "Slovakia", "Slovakia", "Latvia", "Austria", "Ireland", 
    "Luxembourg", "Belgium", "Italy", "Estonia", "Greece", "Slovakia", 
    "Belgium", "Italy", "Latvia", "Malta", "Greece", "France", 
    "Greece", "Netherlands", "France", "Slovenia", "Latvia", 
    "Finland", "Austria", "Slovenia", "Belgium", "Cyprus", "Greece", 
    "Slovenia", "Cyprus", "Finland", "Malta", "Germany"), `1995` = c(274959716, 
    42345007970, 52361033, 784003104, 363593773, 26339142, 70240364.9716237, 
    66160839.8751728, 570402199.020507, 48087089, 7213761, 51841984.7433951, 
    17654753.3588222, 172147969, 510653861, 1490942352, 236034017, 
    21599848, 8237002.21796104, 78753113, 1785782, 317673116, 
    1997651, 191502494, 1085060805, 397894640.417207, 3278854, 
    311533699, 1120849630.02838, 16319437, 83172852.11371, 7429991, 
    1130916439, 37969299820, 893625108.88629, 85666548, 20013832, 
    34463454.0875298, 391203046, 6317180664.31942, 19705368, 
    392268361, 4455785372.87273, 222358956, 411505.596673383, 
    52421883, 15725678.4821813, 1822047157.86885, 2459346931, 
    1876562166, 808113, 1124090, 266044676, 2248412.10389544, 
    7378082, 18441136707, 20732500726.5828, 2916590, 4946996508, 
    1165517054, 737293168, 1253219429, 234340068.782039, 10770159, 
    966929910, 40043392, 1231347, 76204779, 564056237, 152914849, 
    3269662990, 108614454, 2313081.15506869, 1189550231.54615, 
    8097112911, 15174304, 877483944.124827, 2135381409, 28188202490.5877, 
    1524668022, 84865417, 1965397.25660491, 1384674, 3699841535, 
    4383865473, 1233064242, 664865392, 183091, 42970685.557638, 
    4742184966, 550250520, 102947427, 49519226.4265594, 5273729, 
    105863344, 5888705, 10907803, 1170153350, 20869834, 43104477514
    )), row.names = c(NA, -100L), class = c("tbl_df", "tbl", 
"data.frame"))

和

> dput(actors)
c("Slovakia", "Germany", "Portugal", "Austria", "Latvia", "Cyprus", 
"Greece", "Italy", "Slovenia", "Ireland", "Malta", "Luxembourg", 
"France", "Netherlands", "Spain", "Belgium", "Finland", "Lithuania", 
"Estonia")

Answer 1

也许你可以试试这个

graph_from_data_frame(relations, vertices = data.frame(name = actors))

来自数据框的 Dijkstra 算法的最短路径

Shortest Path with Dijkstra’s Algorithm from a dataframe

r

igraph

dijkstra