algorithm - 友情关系追踪算法

Question

我正在考虑一个应用程序，它会尝试用属于社交网络的一组用户来证明“Six degrees of separation”理论。

我会有那些元素:

1. 我想为他们证明六度理论的几个用户
2. 对于每个用户，我知道社交网络中的好友列表

查看两个用户是否连接、连接程度以及显示连接的最终步骤的最佳算法是什么？

Answer 1

寻找社交网络中两个人之间的分离程度只是寻找图中两点之间最短路径的一个特例。最常见的方法是 Dijkstra's algorithm , 但另请参阅对 Shortest path problem 的更长讨论.

此外，通过运行 All-pairs 最短路径算法，您可以找出整个网络的最小、最大和平均分离度数。