我只是在学习图论，并且正在尝试将代码编写为算法问题。问题涉及n组人，每个人与其中一个成员至少有一个相互友谊。问题是找到两个人之间最短的友谊链接。最短的友谊链接包含的人数最少。例如; A 和 B 是共同的朋友，B 和 C 是共同的朋友，如果 A 和 C 也是共同的朋友，那么 AC 和 ABC 是 A 和 C 之间的友谊链接，但 AC 被认为更短，因为它涉及的个人较少。
我想知道在这种情况下适用哪种图论算法，并且我会很感激任何关于图论的免费互联网文档的推荐（维基除外）。
user1372984
问问题
9712 次
1 回答
8
对于两个节点的最短路径的未加权问题-您可以使用BFS，不需要更难实现且效率较低的Dijkstra 算法。
请注意，BFS 的主要问题是空间效率，因为它在O(|V|)空间中运行，它可以通过与 DFS 进行权衡来部分解决，称为迭代深化 DFS。它也将是最佳的，但会消耗更少的空间（以额外的时间为代价）。
情况似乎并非如此，但如果您可以评估您与目标的距离 - 您可以使用A* Algorithm，它具有良好的启发式函数可能会执行得更快。
另请注意：如果您想要所有用户之间的最短距离，您可以使用Floyd-Warshall 算法
于 2013-02-28T16:47:36.677 回答