`igraph` 如何使用 Dijkstra 算法计算加权有向网络中的最短路径？

Question

我想计算网络的介数，例如

>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")
>g <- graph_from_data_frame(relations, directed=TRUE, vertices=actors)

我想使用软件包提供的命令：betweenness(g)。但是我不知道igraph中两个节点之间的距离是如何计算的。它是权重的总和吗？还是权重的倒数之和？

Answer 1

在所有 igraph 函数中，路径的“长度”被认为是构成该路径的边的权重之和。

`igraph` 如何使用 Dijkstra 算法计算加权有向网络中的最短路径？

How does ` igraph` calculate the shortest path in a weighted directed network, using Dijkstra's Algorithm?

r

dijkstra

igraph