PHP 如何计算人与人之间的最短关系

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 3249 days ago, the information mentioned may be changed or developed.

一个数据表，里面分别是某人在某公司工作，现在给出里面的两个人，如何计算出最短的路径，你或你的朋友和另外一个人之间有共同的工作经历。

PHP

计算

路径

给出

31 replies • 2017-07-17 20:06:32 +08:00

ericls

Jul 17, 2017 via iPhone

看看 graph theory

shiji

Jul 17, 2017

这跟 PHP 有直接关系么。。

xiaopc

Jul 17, 2017 via Android

单源最短路问题，Dijkstra 等算法
和语言没关系

globetour

Jul 17, 2017 via Android

@ericls 我查查，感谢

globetour

Jul 17, 2017 via Android

@xiaopc 请教兄弟如何解决呢

qiuyk

Jul 17, 2017

@globetour 搜一下 Dijkstra 应该就够了你要嫌复杂就 DFS 或者 BFS 呗...

lxrmido

Jul 17, 2017

无向图的最短路径问题

lights

Jul 17, 2017 via iPhone

图数据库，或者加一个图算法层

globetour

Jul 17, 2017

@qiuyk
@lxrmido
@lights
感谢，

we3613040

Jul 17, 2017

又黑我大 php

U7Q5tLAex2FI0o0g

Jul 17, 2017

又黑我大 php

orvnge

Jul 17, 2017

和语言无关
判断相似性就可以了曼哈顿，欧几里得距离，预先相似，皮尔逊算法都可以

globetour

Jul 17, 2017 via Android

@orvnge 专业，没做过这种算法，感觉无从下手啊。

Shura

Jul 17, 2017 via Android

楼主是想找个库函数直接就计算出来吗？

iyaozhen

Jul 17, 2017 via Android

楼主把标题里的 php 去掉我们还能做朋友。

你应该说需求，然后再说自己主力开发语言，下面说不定就有人扔 github 链接了

globetour

Jul 17, 2017 via Android

@Shura 还是兄弟理解我

globetour

Jul 17, 2017 via Android

@iyaozhen 好像去不掉了

orvnge

Jul 17, 2017

@globetour 如果是简单判断相似性的话其实这几种算法就是求两点距离很容易理解代码也很好弄，你可以搜索看看

globetour

Jul 17, 2017 via Android

@orvnge 不是简单相似，需要这种结果，比如
用户 a
同在公司 a 工作
用户 b
同在公司 b 工作
用户 c
同在公司 c 工作
用户 d

就是说用户 a 与 d 之间找到一个最短的路径算法。

cxbig

Jul 17, 2017 via iPhone

试试 Neo4j ？

globetour

Jul 17, 2017 via Android

@cxbig 图形数据库？

cxbig

Jul 17, 2017 via iPhone

@globetour 对，擅长处理 object 之间的关系。

globetour

Jul 17, 2017 via Android

@cxbig 学习了

murusu

Jul 17, 2017

最近也在找相关资料，估计楼主跟我在弄的东西有点类似

globetour

Jul 17, 2017 via Android

@murusu 你 q 多少，加一下

solaro

Jul 17, 2017

猜测楼主在脉脉之类的公司

globetour

Jul 17, 2017 via Android

@solaro 个人瞎搞，真的，这个对于大公司应该不难搞吧

liuhaotian

Jul 17, 2017 via iPhone

这种关系图应该是稀疏图吧
Dijkstra 够了

globetour

Jul 17, 2017 via Android

@liuhaotian 我看 Dijkstra 都是用于算节点之间的具体数值的距离，没看到怎么去算两个人之间最短关系路径的例子呢，比如没办法量化每个节点与公司之间的数值啊！

stone1342006

Jul 17, 2017

@globetour 初始化所有人之间都是无穷远，曾经有过共同工作经历的可以加一条长度为 1 的边啊，就阔以初始化这个图了

globetour

Jul 17, 2017 via Android

@stone1342006 容我消化一下