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

[globetour]

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

[ericls]

看看 graph theory

[shiji]

这跟 PHP 有直接关系么。。

[xiaopc]

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

[globetour]

@ericls 我查查，感谢

[globetour]

@xiaopc 请教兄弟如何解决呢

[qiuyk]

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

[lxrmido]

无向图的最短路径问题

[lights]

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

[globetour]

@qiuyk
@lxrmido
@lights
感谢，

[we3613040]

又黑我大 php

[littleylv]

又黑我大 php

[orvnge]

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

[globetour]

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

[Shura]

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

[iyaozhen]

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

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

[globetour]

@Shura 还是兄弟理解我

[globetour]

@iyaozhen 好像去不掉了

[orvnge]

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

[globetour]

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

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

[cxbig]

试试 Neo4j ？

[globetour]

@cxbig 图形数据库？

[cxbig]

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

[globetour]

@cxbig 学习了

[murusu]

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

[globetour]

@murusu 你 q 多少，加一下

[solaro]

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

[globetour]

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

[liuhaotian]

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

[globetour]

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

[stone1342006]

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

[globetour]

@stone1342006 容我消化一下