算法 - 朋友的朋友

Question

算法 - 朋友的朋友

5

我正在学习图论，并试图编写一个算法问题的代码。这个问题涉及到n组人，每个人都至少与其中一名成员有共同的友谊关系。问题是找出两个人之间最短的友谊链接。最短的友谊链接包含最少的人数。例如：A和B是互相的朋友，B和C也是互相的朋友，如果A和C也是互相的朋友，则A-C和A-B-C是A和C之间的友谊链接，但A-C被认为更短，因为它涉及更少的人。

我想知道哪些图论算法适用于这种情况，并且我会感激任何关于图论的好的免费互联网文档（除维基百科之外）的推荐。

- user1372984

4

这里可以使用任何最短路径算法。参考 Dijkstra 算法，或者 Bellman-Ford 算法。 - phoeagon

@phoeagon 如果有缺失的链接，它就不会起作用，请重新阅读问题。我认为应该使用传递闭包。 - axiom

你说：“每个人都至少与其中一位成员有一种互相的友谊”，那么这组 {A-B C-D} 怎么办？如果 A 和 C 之间没有联系怎么办？ - Alexander Van Atta

@phoeagon 可能存在一条边A-B和一条B-C。最短路径算法将给出答案A-B-C。在我们能够评论之前，我们需要添加边A-C。这就是问题所在。可以通过计算邻接矩阵的所有幂并取并集来解决此问题。需要进行n次Dijkstra迭代吗？ - axiom

也许吧，但评论中有很多提示。应该对提问者足够了。 - axiom

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

对于两个节点的最短路径的无权问题 - 您可以使用 BFS，不需要 Dijkstra's algorithm，后者难以实现且效率较低。

请注意，BFS 的主要问题是空间效率，因为它在 O(|V|) 空间中运行，可以通过与 DFS 的折衷来部分解决，称为 迭代加深搜索(IDDFS)。它也将是最优的，但会消耗更少的空间（代价是额外的时间）。

如果你能评估自己距离目标有多接近，即使看起来不是这样，你也可以使用A*算法，如果给定一个良好的启发式函数，它可能会执行得更快。

还要注意：如果你想要所有用户之间的最短距离，可以使用Floyd-Warshall算法。