3

我在大数据分析中遇到了一个问题，我正在使用 Dijkstras 算法找出具有超过 175K 个节点的图的路径。但问题是我不知道特定源和目的地是否存在路径。我必须为大约 1000 个来源和目的地执行此操作。但是我不能随机选择它们，因为我不确定它们之间是否存在路径。我不确定如何处理。在 MapReduce 环境中执行一次算法在本地需要大约 15 分钟的时间。因此，反复试验不是一种选择。只有我能找到至少 1000 个源和目标是找到循环（？）或强连接组件？这个对吗 ？我希望我的问题很清楚。

我基本上是在寻找说 1000 对源和目的地，它们的路径存在于该大小的图中

4

3 回答 3

4

我建议随机挑选 1000 个源节点，然后为每个节点运行广度优先搜索，直到您访问过k节点。然后，选择您要访问的下一个节点并将其设置为该源的目的地。

使用这种方法，您可以确保每个目的地都可以从该来源到达。

于 2012-12-04T03:10:59.320 回答
3

我们可以使用像 disjoint-union-set(DUS) 这样的数据结构。我们进行初始化以获得整个图的连通性。如果 a 可以到达 b，它们将位于 DUS 中的同一组中。初始化的复杂度完全取决于图中的边数。查询是关于 O(1) 的。

于 2012-12-04T04:14:23.633 回答
0

这是我建议的算法：

findPairsPath ()
{
    define 2D Array SD //holds source-destination nodes
    SD = {}
    pick any node u randomly
    k=0

    while (k<1000)
    {
       DFS (u, k)
       pick any node u randomly not stored in SD 
    }
}

DFS (u, k)
{

    for all nodes v adjacent to u and not stored in SD
     {
       store (u,v) in SD //storing a source and a destination
       k++
       DFS (v,k)

     }

}
于 2012-12-25T22:18:36.443 回答