如何找到两个抽象节点之间的路径

Question

我想测试“小世界”或“六度分离”假设，即任何人都可以通过6个共同的朋友到达另一个人的理论。(即朋友的朋友)

示例节点数据(JSON)：

{
    "name": "John Smith",
    "friends": [
        "Foo Bar",
        "John Doe"
    ]
}

将会有成百上千个这样的对象，每个对象都相互链接。我想找出他们之间的最短路径。像那些在游戏中发现的寻路算法是否适合于这样的抽象概念(即:在2D或3D世界中无法表示的概念)，或者是否有更优雅的解决方案？

我知道，随着搜索深度的增加，我可以多次遍历好友列表，但这将是一个不优雅的解决方案，需要花费大量数据很长时间。

我已经很清楚像A*这样的寻路算法，但我只是不确定这是否适合使用它们

至少，程序应该输出这样的字符串：“从person1到person2需要x个步骤”如果能了解中间人，甚至可以从中获得一个很好的web/图形，那将是一件很好的事情。

Answer 1

此链接Finding Paths in Graphs (第33，34页)为您提供了一个强大的图形算法，您可以假设这些是小世界的图形！

在实现算法之前，您应该将json数据转换为具有合理快速数据结构(密集与稀疏图形表示)的图形。

Answer 2

你可能想看看所有节点的Floyd Warshall，最短的paths.Complexity是O(N^3)

或者，您可以从每个节点运行djikstra并在O(ElogV * N)时间内计算它

下面是一个很好的实现http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/