★ FEATURED ARTICLE 1. 从六度人脉到图论建模这个问题的本质是什么做社交网络分析的人十有八九都听过六度人脉这个说法——世界上任何两个人之间平均只需要经过大约6次人际关系跳转就能建立联系。我第一次对这个问题产生动手算一算的冲动是在一次内部工具开发时产品经理提了个需求说想在通讯录App里加一个好友的好友的好友推荐入口最好能直观显示你和目标用户之间隔着几层关系。当时第一反应是直接写个广度优先搜索完事但仔细一想需求里还藏着一句如果能顺便告诉我每一步怎么走就更好了这就从判断是否可达升级成了求解并还原最短路径。于是Floyd算法进入了我的视野。六度人脉在计算机科学里不是玄学而是典型的图论问题。把人抽象成节点把人与人之间的直接社交关系抽象成边整个社交网络就是一张巨大的带权图。所谓六度本质是在问这张图里任意两个节点之间的最短路径长度平均是不是真的在小常数范围内早在20世纪60年代Stanley Milgram的连锁信实验就给出了一个经验答案——约6跳。到了后来小世界网络理论进一步解释了这种现象即使节点总数n非常庞大只要网络具备较高的聚类系数和较短的随机长程连接任意两个节点之间的最短路径长度l仍然保持在log n级别的量级。用人话说就是节点再多靠少数几个社交枢纽就能把距离急剧拉近。这个现象对算法选型有直接影响。如果社交网络真的是小世界网络那意味着多数节点对之间的最短路径其实很短可能只有3到8跳。这个特点让我们在设计六度人脉查询系统时既要考虑算法的准确性又不得不考虑规模带来的工程压力。Floyd算法虽然以三重循环和O(n³)时间复杂度著称放在全网级别的社交网络上跑显然不现实但在特定场景下——比如企业组织内部通讯录、垂直社区的核心用户群、学校校友网络——它依然是目前我个人最喜欢的方案之一原因后面会详细展开一是简单二是能一次性算出所有节点对的最短路径三是配合路径重建逻辑可以拿到完整的传递链非常适合批量预计算在线查询的架构。在动手写代码之前先把问题的图论模型说清楚。社交网络在数学上可以表示为一个无向带权图G(V,E)V是用户集合E是关系集合。如果只看好友关系是否存在权重可以直接设成1此时最短路径就是最少跳数如果还要考虑互动频率、亲疏程度权重可以设成1/互动次数之类的倒数此时最短路径代表最紧密的关联链。我们需求里最常见的是前一种——先求最少跳数再考虑关系强度作为辅助排序。当然图模型的建立还涉及一个比较关键的问题方向性。微博的关注是有向的你关注了对方不代表对方关注了你微信的好友是无向的双方确认才建立关系。如果项目需求是找到你可以通过哪些人触及某个目标用户那路径方向必须考虑进去此时邻接矩阵不再对称Floyd算法依然适用但需要保证边的方向建模正确。我在实际开发中就踩过这个坑——早期图省事把关注关系当成无向边处理导致推荐结果里出现了你单方面关注的人被算成了双向好友这种逻辑错误。2. Floyd算法的原理解读为什么它能一次算出所有人之间的最短路径2.1 核心思想动态规划与中转站假设想要在社交网络里找到任意两个人之间的最短路径最直接的思路是枚举所有可能的中间人组合。比如从A到C可以考虑A直接认识C也可以考虑A先经过B1再到C或者经过B1、B2再到C。问题是中间人的组合数量爆炸增长不可能全部枚举。Floyd算法的聪明之处在于用动态规划避免了这种组合爆炸。它把问题重新定义为从节点i到节点j的最短路径要么不经过任何中转站要么经过若干个中转站其中中转站的编号都在一个逐渐扩大的集合内。算法逐步允许中转站集合从空集扩大到包含全部节点每次引入一个新节点k时检查从i到k的最短距离 从k到j的最短距离是否比当前记录的i到j最短距离更短。如果是就更新。这个逐个放行中转站的思路本质上和中学数学里的归纳法很像已知在只允许使用前k-1个节点作为中转站的情况下所有节点对之间的最短距离dist[i][j]现在允许使用第k个节点作为中转站那新的最短距离要么保持原样不经过k要么是dist[i][k] dist[k][j]经过k取较小值即可。写成状态转移方程就是dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。这个递推式是Floyd算法的心脏也是全篇代码里唯一真正核心的公式。它不需要递归不需要贪心策略只需要三重循环一层层刷新矩阵最终dist矩阵里存储的就是任意两点间的最短路径距离。我当年第一次看到这个算法时最大的震撼就是一个这么复杂的全局问题居然用三行嵌套循环就解决了而且对负权边只要没有负权环也能正确处理这是Dijkstra算法做不到的。2.2 距离矩阵与路径矩阵不仅要算得出来还要还原得回去很多入门教程只讲dist矩阵的更新却忽略了另一个关键矩阵——next矩阵有些资料里叫path矩阵。dist矩阵告诉我们两点之间最短距离是多少但如果我们还想展示A是怎么到C的就必须额外维护路径信息。路径还原的思路也来自动态规划每次我们决定通过中转站k来缩短i到j的距离时就把next[i][j]记为next[i][k]。这样到最后next[i][j]存储的就是从i出发到j的路径上的第一个中转节点。这里有个细节需要特别注意next[i][j]记录的并不是j本身而是路径上i的下一个节点。如果要还原完整路径需要反复跳转cur i循环记录curcur next[cur][j]直到cur等于j为止。以社交场景举例如果想找我——张三——李四——王五——目标用户这条路径dist矩阵给出4这个跳数next矩阵则负责一步步还原出张三、李四、王五这些具体中间人。缺少这一步算法就只能给一个你们之间最短隔了4层的结论而产品经理和用户真正想看到的是你认识谁、谁认识谁、最终通过谁联系上。这是我在实际项目中第二次踩坑的地方最开始只实现了dist矩阵测了好几天才发现最短跳数是算出来了但根本没法把路径中间节点展示出来等于白做了一半工作。2.3 一轮循环做一次中转站放行逐步逼近最优解为了更直观地理解Floyd算法的执行过程可以把三重循环比作一个逐渐严密的关系网络编织过程。第一层循环k从0遍历到n-1每轮相当于把编号为k的节点升级为合法中转站。在每一轮中第二层循环i和第三层循环j则把所有节点对都检查一遍看看有没有必要让k来充当它们之间的桥梁。举个例子假设现在网络里有4个人0号、1号、2号、3号。刚开始的dist矩阵就是原点之间关系边的权重矩阵没有边的地方填无穷大。当k0时算法只允许把0号作为中转站如果从1号到2号没有直接边但从1号到0号有边、从0号到2号也有边那么dist[1][2]就会被更新为这两段之和。当k1时又把1号纳入中转站集合此时从0号到3号如果原来没路但0号经过1号到3号有路那dist[0][3]也会被刷新。这个过程每进行一轮中转站的候选池就扩大一个已计算出的dist矩阵就越来越接近真正的全局最优。等k循环到最后一轮中转站集合已经涵盖所有节点时dist矩阵里的每一个值都是对应节点对之间的最短距离。从算法正确性的角度讲Floyd算法的关键在于任意一条最短路径上的所有中间节点都会按照编号逐一被放行进来而一旦某个中转站被放行依赖它的路径组合就会被尝试一遍并记录下来。由于每个节点最终都会被放行所有可能成为最短路径中间节点的节点都不会被遗漏因此最终的dist矩阵必然收敛于正确结果。3. 实战动手用Python实现社交网络中的六度人脉计算3.1 构建社交关系邻接矩阵纸上谈兵聊完原理直接进入能跑的代码。为了让例子贴近真实项目我构造一个mini社交网络数据集10个用户按社交关系连了一些边边的权重都设成1。之所以用权重1是因为六度人脉这个场景里我们关心的是最少跳数——每经过一个中间人路径长度加1跳数就是权重之和。当然如果你的产品里需要把互动频繁程度纳入考量完全可以换成0.5、0.2这样的小数权重算法本身不需要改动。代码第一步是构建邻接矩阵。我们用一个n x n的二维列表来存储距离初始时节点到自身的距离是0有直接好友关系的节点对距离是1其余全部设为一个很大的数代表暂时不可达。import numpy as np def build_adjacency_matrix(n, edges): 构建社交网络的邻接矩阵。 n: 用户数量 edges: 列表每个元素是 (u, v)表示用户u和用户v是好友无向边 INF float(inf) dist [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] 0 for u, v in edges: dist[u][v] 1 dist[v][u] 1 # 无向关系对称赋值 return dist # 一个模拟的好友关系数据集 edges [ (0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (5, 9) ] adj_matrix build_adjacency_matrix(10, edges)这里有个值得说明的小决定为什么用Python的list而不是NumPy数组对于10个节点的demo来说list足够清晰也方便初学者看数据。但如果你后续要处理几百上千个节点强烈建议改用NumPy数组并用np.minimum来加速矩阵逐元素比较否则纯Python的三重循环在节点数过千后会慢到让人怀疑人生。在下面的实现中我会先用纯Python把逻辑讲清楚再给出一个NumPy加速版。3.2 实现Floyd核心算法并还原最短路径核心算法部分按前文说的拆成两个矩阵dist矩阵存最短距离。next矩阵存路径还原信息。初始时如果i到j有边next[i][j]设为j表示从i出发直接到j。如果没有边且i不等于jnext[i][j]设为-1代表不可达。def floyd_with_path(dist_matrix): n len(dist_matrix) INF float(inf) # 初始化next矩阵 next_matrix [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if dist_matrix[i][j] ! INF and i ! j: next_matrix[i][j] j # Floyd三重循环 for k in range(n): for i in range(n): for j in range(n): if dist_matrix[i][k] dist_matrix[k][j] dist_matrix[i][j]: dist_matrix[i][j] dist_matrix[i][k] dist_matrix[k][j] next_matrix[i][j] next_matrix[i][k] return dist_matrix, next_matrix def reconstruct_path(next_matrix, start, end): 根据next矩阵还原从start到end的完整路径 if next_matrix[start][end] -1: return None path [start] cur start while cur ! end: cur next_matrix[cur][end] path.append(cur) return path dist_matrix, next_matrix floyd_with_path(adj_matrix) # 输出用户0到用户9的最短路径 path_0_9 reconstruct_path(next_matrix, 0, 9) print(用户0到用户9的最短跳数:, dist_matrix[0][9]) print(完整路径:, - .join(map(str, path_0_9)))运行这段代码你可能会得到类似0 - 1 - 3 - 5 - 9这样的输出意味着从用户0到用户9隔了4跳路径是经过用户1、用户3、用户5到达用户9。这就是六度人脉里一个具体的人脉链路。把用户替换成真实姓名再把路径展示到前端页面上产品经理要的功能就完成了。3.3 从是否可达到最近距离两种场景的选择实际项目中最短路径问题往往细分为两类需求第一类只关心两个人之间是否连通以及如果连通最少隔几层。这类需求用Floyd算法有些大材小用因为只需要求单个源点到其他所有点的最短距离用BFS无权图或Dijkstra带权图就够了时间复杂度O(n²)或O(mlogn)远比O(n³)快。第二类关心任意两个人之间的最短路径而且这种查询会高频出现。比如企业内部知识库中想知道任意两个员工之间通过什么协作关系链可以建立联系或者相亲平台中想实时推荐你和看中的那个人之间有什么共同认识的人。这类需求如果用BFS逐一查询每次都要从源点出发跑一遍遍历当查询量大到一定程度后总耗时反而不划。Floyd算法把全局所有节点对的最短路径提前算好存在矩阵里后续每次查询只需要O(1)查表是一个典型的空间换时间、预计算换查询策略。我踩过的一次项目教训是一开始我用Dijkstra做了单点查询产品验收时发现没问题但等真实用户量上来每天几百万次六度人脉查询服务直接把后端CPU打满。后来改成Floyd预计算启动时跑一次全量计算当时节点规模只有几千人跑完大概几十秒后续查询全部变成查矩阵CPU占用直接降了两个数量级。所以千万不要一看到O(n³)就否定Floyd关键要看业务流量是一次性全量计算还是频繁多次查询。如果是后者Floyd反而可能是最优解。4. 复杂度优化与工程落地当节点数量膨胀时该怎么办4.1 深入分析O(n³)的时间损耗到底花在哪把Floyd算法部署到真实社交网络前必须直面一个问题O(n³)到底能不能承受假设社交网络有1万个节点三重循环就是10^12量级的基本操作在普通服务器上可能要跑几个小时。如果再大一点像真实社交平台动辄几千万用户O(n³)完全不可行。不过仔细分析一下O(n³)的常数因子很小而且三重循环内部操作极其简单就是一个加法一次比较一次赋值。在Python里瓶颈很明显但如果用C语言或NumPy向量化速度能提升几个数量级。以1000个节点为例numpy版本的Floyd在一台普通笔记本上不到一秒就能跑完哪怕到5000个节点也能在几十秒内完成。很多企业内部的社交网络、校园网、医院内部协作网节点量也就这个量级分立一个小服务专门做预计算完全没问题。另外要留意的是矩阵的初始化。用float(inf)表示无穷大在Python里非常方便但当dist_matrix[i][k]本身就是inf时再和dist_matrix[k][j]相加Python的浮点运算规则会得到inf再进行比较时不会出错。不过如果节点数大建议把INF设成一个足够大的有限整数比如10**9这样既可以避免浮点运算的额外开销也能防止某些环境下inf参与运算时出现的性能波动。4.2 用小世界网络特性做工程上的取舍前面提到小世界网络的关键特性即使节点总数n很大平均最短路径长度l依然是对数级别。这个特性在工程上可以帮我们做一件重要的事控制中转站的枚举范围。Floyd算法之所以是O(n³)是因为它对每一个可能的中转站k都做全面检查。但如果社交网络确实是小世界网络任意两个节点之间的最短路径其实并不长不需要在每一轮循环里都遍历所有节点。一个工程近似是把网络划分成社区先在社区内部跑Floyd再对社区之间的连接关系跑一次粗粒度Floyd最后把两层结果拼接起来。社区内部的节点数通常几百到几千跑起来毫无压力社区数量虽然多但社区之间的连接往往相对稀疏粗粒度Floyd也能接受。这个先局部后全局的思路在大型社交网络项目里非常实用。当然引入社区划分后结果是近似最优而不是严格最优在某些跨社区的路径上可能不是真正的最短路径。这需要产品层面做一个明确取舍是要绝对精确还是秒级响应。就我服务过的几个项目而言用户对六度人脉的期望本来就更倾向于快速看到一条合理的传递链而不是每一次都证明这就是全局最短。这其实也符合小世界网络的理论结果——即使偶尔不是严格最短多出来的路径长度通常也就一两条边而已完全在可接受范围内。4.3 空间优化只保留路径矩阵减少存储压力Floyd算法另一个常被忽视的问题是空间占用。dist矩阵和next矩阵都是n x n每个元素如果是整数或浮点数节点数量稍大就会吃掉不少内存。1万个节点两个矩阵各需要1亿个元素按每个元素4字节算就是800MB很紧张。如果只关心最短距离而不需要还原路径可以直接丢掉next矩阵只保留dist矩阵空间减半。如果既要距离又要路径但内存依然紧张可以考虑一种折中方案路径还原时不存完整的next矩阵而是只存储路径上的下一跳节点这在很多场景下可以用更紧凑的邻接表或字典结构实现。还有一种工程上常见的做法把计算好的dist矩阵和next矩阵序列化到磁盘或Redis里服务启动时按需加载。这样即使预计算时间较长也可以放到后台任务中执行计算完再热更新用户查询完全不受影响。我在实际项目中就用过这个方案——每天早上定时跑一次全量Floyd结果写入Redis白天的所有六度人脉查询直接读缓存日活几千人的内部系统运行得非常稳定。5. 权重设计当最短路径不再是最少跳数时5.1 关系强度的量化方式纯粹的最少跳数适合验证六度人脉理论但真实产品几乎不会只用跳数来衡量人脉远近。两个人的直接好友关系有天天聊天的铁哥们也有三年没说过话的点赞之交。如果路径上每一跳的质量不同最短路径的定义就需要调整。比较常见的做法是把关系强度映射成一个数值再转换成权重。比如统计近30天内两个用户之间的私聊消息数、点赞数、共同群聊数综合打分得到一个亲密度s然后定义边权重w 1 / (s 1)。这里加1是为了防止除零同时保证当亲密度极低时权重不会无穷大。这样一来权重越小代表关系越紧密Floyd算法算出的最短路径就是总亲密度损失最小的路径更接近真实世界的最佳引荐链。实现上只需要在构建邻接矩阵时把无权重的1替换成计算出的权重即可。需要注意权重必须是非负数。Floyd算法对负权边是可以处理的但不能有负权环因为负权环会让最短路径不断绕圈变小变成负无穷。社交网络的权重设计里不应该出现负值这点其实不用担心。5.2 结合六度阈值的剪枝策略六度人脉这个概念本身就暗示了一个心理学和社会学上的阈值超过6跳的关系对用户来说已经不太有实际搭桥意义了。产品设计时完全可以利用这个阈值对算法做剪枝不必跑完所有节点对。做法很简单设置一个最大距离max_dist6在Floyd循环里如果dist[i][k]已经大于等于max_dist就跳过j循环同样如果dist[k][j]已经大于等于max_dist也没有必要再更新。这个剪枝虽然不能改变最坏复杂度O(n³)但在小世界网络中能大幅减少实际循环次数因为大部分节点对的最短路径长度本来就远小于6一旦超过6这个不关心阈值继续计算纯属浪费。我做一个校友人脉检索系统时就用了这个策略整个网络约2000个节点跑了剪枝版Floyd后计算时间从原来的十几秒降到了三秒以内。给产品同学解释这个优化时我说用户根本不想看一条20跳的人脉链那在现实里毫无意义我们只要保证6跳以内的路径是准确且完整的就行了。这一点在很多需求评审中反而比算法本身更容易打动业务方。5.3 有向图场景下的路径方向处理现实中的社交关系不总是双向的。微博、领英、脉脉这些平台的核心关系是有向的A关注了B不代表B关注了A。如果产品想展示的是你可以通过哪些人一步步触达到目标用户那么图模型必须是有向带权图。Floyd算法本身天然支持有向图因为它的状态转移方程不要求dist矩阵对称。只要在建图时保持方向正确——dist[u][v]存的是从u到v的边权重dist[v][u]如果是无边就留INF——算法就能正确计算有向图下的最短路径。真正容易出错的地方在于路径还原和前端展示在有向场景里next矩阵记录的方向是从当前节点指向目标节点的方向不能随意反转否则会出现逻辑上的循环引用或路径断裂。分享一个我实际遇到的问题。有段时间做职场社交产品的二度人脉功能QA测试时发现路径还原结果里出现了我 - A - 我这样的循环。排查了半天原因是有向图构建时把互相关注的关系存了双向边而单向关注的关系只存了单向边这本身没错但next矩阵初始化时我代码里图省事把所有dist[i][j] ! INF 的next[i][j]都设成了j对于有向边来说这没问题可随后某次更新里next[i][j]被覆盖成了next[i][k]而k到j方向并不存在可达边导致路径还原死循环。后来在reconstruct_path里加了访问次数上限保护超过n次直接判为异常路径并丢弃问题才稳定下来。这个坑很隐蔽建议读者在实现路径还原时无论如何都加一层循环保护不要假设算法输出永远正确。6. 工程实践中的三种常见性能优化手段6.1 用NumPy向量化内层循环纯Python的三重循环逻辑清晰但性能很一般。如果语言选Python又想跑上千个节点的Floyd强烈建议用NumPy重写内层循环。import numpy as np def floyd_numpy(dist): n dist.shape[0] for k in range(n): # 利用广播机制一次性更新所有 i, j dk dist[k, :] # 从k到所有节点的距离向量 di dist[:, k].reshape(-1, 1) # 从所有节点到k的距离向量转为列 candidate di dk # 这就是 dist[i][k] dist[k][j] 的矩阵版 dist np.minimum(dist, candidate) return dist这段代码把内层的i和j两层循环交给了NumPy的C语言实现速度提升非常明显。需要注意candidate计算时di的reshape操作如果省略广播机制很可能因为维度不匹配而报错或产生错误结果。还有一个隐藏的坑np.minimum是对整个矩阵做逐元素比较并生成新数组会带来额外内存分配。如果n很大建议使用dist np.minimum(dist, candidate, outdist)直接覆盖原数组减少内存抖动。举个实测数据纯Python三重循环跑500个节点大概需要几十秒NumPy版跑1000个节点也只要一两秒。优化效果完全值得你花几分钟改一下代码。6.2 多线程/多进程并行预计算Floyd算法的三重循环外层是k每一轮k都需要依赖上一轮k-1的结果看起来没法并行。但如果我们对问题做额外变通把节点集合做成分块或分社区各社区之间就可以并行计算。更简单的工程优化方案是同时对多个规模较小的社交子图分别跑Floyd最后合并结果。举个例子一个企业通讯录可能有2万员工但按照部门划分成几十个子图后每个子图只有几百人。部门内部用Floyd精确计算部门之间用BFS或Dijkstra做桥接整体方案在近似的代价下获得了几乎线性的加速比。我用multiprocessing.Pool跑过类似任务8核机器上速度提升大概5到6倍效果稳定。不过在数据合并时要格外小心跨子图的路径可能不是严格全局最优这一点我建议在方案设计阶段就和业务方对齐避免验收时被质疑算法结果不对。6.3 用缓存与增量更新应对动态社交网络真实社交网络是动态的——每天都有新用户加入新好友关系建立也可能有人删除好友。Floyd预计算的全局结果会随图的变化而过期。如果每次变化都重算全图成本太高完全不重算查询结果又会很快失真。我的经验是采用两级缓存策略底层存储全量预计算的dist矩阵与next矩阵定时全量刷新上层增加一个增量更新层记录最近一段时间内变化的边查询时先把变化边的影响合并到预计算结果中再返回。这里合并的逻辑可以简单实现为先用老矩阵dist给出初步最短距离d然后逐一尝试新加的边(u, v, w)看dist[s][u]wdist[v][t]是否小于d如果小于就更新答案。这种方法虽然不是完全精确但对六度人脉这种容错度较高的业务场景来说完全够用。实际项目中我还加过一层周期性重算的调度晚上业务低峰期跑全量Floyd白天增量更新兜底。这套方案支撑过几万节点、每天百万次查询的在线服务单机稳稳扛住几乎没有出现超时告警。7. 常见问题排查与避坑实录7.1 邻接矩阵对角线为什么必须初始化为0这个问题很多初学者会忽略。对角线的含义是节点到自身的最短距离。在社交网络里一个人到自己当然是0跳不需要经过任何人。如果把对角线也初始化为INFFloyd计算时可能把从i到i的距离错误地更新为一条环路的长度。比如i到j有边j到i也有边算法可能算出dist[i][i] 2这明显是错的。所以初始化时我习惯单独做一步把dist[i][i]全部设为0。另一个相关坑是后续更新dist[i][i]时如果出现了比0更小的值意味着网络中出现了负权环需要立刻报警排查正常社交网络权重下不应该发生。7.2 路径还原时的循环保护机制前面提到过因为next矩阵的更新逻辑比较绕极端情况下可能构建出包含循环的路径。这在有向图场景下尤其容易出现。建议在reconstruct_path里加一个计数器最大循环次数为节点总数n一旦超出直接返回None并打日志。这个保护不仅能避免程序卡死还能帮助你在开发期尽早暴露next矩阵的更新逻辑错误。7.3 大数据量下的内存与响应时间平衡如果你处理的社交网络规模真的很大比如达到几十万个节点O(n³)和O(n²)空间无论如何都不合适。这时要果断抛弃全局Floyd改用两段式查询架构第一阶段用社区发现算法比如Louvain把大图拆成若干个可计算的社区第二阶段在社区内用Floyd做好预计算社区间用多源BFS或Dijkstra做桥接查询。这种混合方案在工程界已经是比较成熟的套路既能保证社区内部路径精确又能把全网查询控制在秒级响应。牺牲的是社区间路径的理论最优性换来的是系统在真实流量下活下来。对绝大多数六度人脉类产品而言这个交换非常划算。我在多个项目里反复调整过这套方案只要社区划分质量不太离谱业务指标和用户满意度都保持得很好。7.4 结果验证怎么确认Floyd计算没有出错在把Floyd算法结果交给业务方之前我习惯写一个小型验证脚本随机抽N对节点用BFS在无权图上求解最短跳数与Floyd的dist矩阵对比不一致就打印出来。至少抽样1万对以上全部一致才认为是可信的。这个方法在算法刚写完、准备接业务时特别有用能最快发现建图错误或next矩阵更新逻辑问题。对带权图场景则用Dijkstra做抽样对比逻辑类似。建议开发者在项目排期里给结果验证留出少则半天多则一天的时间它帮你省掉的是上线后无数个被用户投诉的夜晚。8. 从六度人脉到推荐系统Floyd算法之外的一点扩展想法聊了这么多实现细节最后分享一点我个人的延伸思考。Floyd算法给出任意两人之间的最短路径这个能力天然适合做社交推荐的解释模块。现在很多平台的好友推荐只告诉用户你可能认识谁却不告诉用户为什么推荐这个人。如果背后有现成的next矩阵就可以直接生成一条引荐链你和目标用户之间隔着你的同事张三张三认识目标用户的前同事李四。这种解释性推荐比生硬的你可能认识有效得多。这种扩展不需要重新设计算法只需要把预计算成果复用起来。比如在做二度人脉推荐时查dist矩阵发现距离为2再用next矩阵还原出唯一的中间人推荐理由就自动生成了。做三度人脉分析时路径还原成完整链展示你认识AA认识BB认识目标用户C这比简单列一堆用户更有说服力。我在实际工作中还尝试过把Floyd的dist矩阵输入到聚类算法里把社交距离作为特征做用户分群效果也比单纯用网络拓扑特征要好一些。这说明Floyd绝不只是作业里背下来的算法它在真实业务里有很多低成本的二次利用方式。只要初心是解决人与人的连接这个问题Floyd总能找到一个不被替代的位置。
阅读完成 · 觉得有帮助？
