主页 / coding / 问题 / 79182778
Accepted
farrow90
Asked: 2024-11-13 05:35:23 +0800 CST

计算图上多个点之间的最短距离？

  • 772

我在 R 中有一个随机图：

library(igraph)
library(tidyr)

set.seed(123)
g <- sample_gnm(n = 20, m = 20, directed = FALSE)

在此处输入图片描述

我正在尝试找出每个节点到每个节点之间的最短距离。

我在 igraph 中找到了一个名为 distances() 的函数并尝试实现它：

dist_df <- as.data.frame(distances(g)) %>%
    mutate(node_i = 1:nrow(.)) %>%
    pivot_longer(cols = -node_i,
                 names_to = "node_j",
                 values_to = "distance") %>%
    mutate(node_j = as.numeric(gsub("V", "", node_j))) %>%
    select(node_i, node_j, distance)

手动检查结果，它们似乎是正确的：

# A tibble: 400 × 3
   node_i node_j distance
    <int>  <dbl>    <dbl>
 1      1      1        0
 2      1      2        2
 3      1      3        3
 4      1      4        4
 5      1      5        4
 6      1      6        3
 7      1      7      Inf
 8      1      8        3
 9      1      9      Inf
10      1     10      Inf

我的问题是： distance() 函数如何能够如此快速地工作？我认为找出图表中的最短路径是一个非常计算密集的过程 - 这个函数如何如此快速地完成它？这是解决此问题的正确函数吗？

1 个回答

  1. Best Answer

    如果你对“为什么”感到好奇，我建议你参考源代码?distances（我不是图论专家，但希望下面的代码可以给你一些线索）

    > distances
function (graph, v = V(graph), to = V(graph), mode = c("all", 
    "out", "in"), weights = NULL, algorithm = c("automatic", 
    "unweighted", "dijkstra", "bellman-ford", "johnson", "floyd-warshall")) 
{
    ensure_igraph(graph)
    if (!is_directed(graph)) {
        mode <- "out"
    }
    v <- as_igraph_vs(graph, v)
    to <- as_igraph_vs(graph, to)
    mode <- igraph.match.arg(mode)
    mode <- switch(mode, out = 1, `in` = 2, all = 3)
    algorithm <- igraph.match.arg(algorithm)
    algorithm <- switch(algorithm, automatic = 0, unweighted = 1,
        dijkstra = 2, `bellman-ford` = 3, johnson = 4, `floyd-warshall` = 5)
    if (is.null(weights)) {
        if ("weight" %in% edge_attr_names(graph)) {
            weights <- as.numeric(E(graph)$weight)
        }
    }
    else {
        if (length(weights) == 1 && is.na(weights)) {
            weights <- NULL
        }
        else {
            weights <- as.numeric(weights)
        }
    }
    if (!is.null(weights) && algorithm == 1) {
        weights <- NULL
        warning("Unweighted algorithm chosen, weights ignored")
    }
    on.exit(.Call(R_igraph_finalizer))
    res <- .Call(R_igraph_shortest_paths, graph, v - 1, to -
        1, as.numeric(mode), weights, as.numeric(algorithm))
    if (igraph_opt("add.vertex.names") && is_named(graph)) {
        rownames(res) <- V(graph)$name[v]
        colnames(res) <- V(graph)$name[to]
    }
    res
}

    您可以看到有几种算法选项，它们的源代码可以在https://github.com/igraph/igraph/tree/master/src/paths中找到

    也许你应该阅读这些文件，我相信你会自己得出结论。

    • 1

相关问题