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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2677 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

PHP

计算

路径

给出

31 条回复 • 2017-07-17 20:06:32 +08:00

ericls

2017-07-17 04:25:35 +08:00 via iPhone

看看 graph theory

shiji

2017-07-17 05:36:05 +08:00

这跟 PHP 有直接关系么。。

xiaopc

2017-07-17 05:50:36 +08:00 via Android

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

globetour

2017-07-17 06:18:21 +08:00 via Android

@ericls 我查查，感谢

globetour

2017-07-17 06:18:48 +08:00 via Android

@xiaopc 请教兄弟如何解决呢

qiuyk

2017-07-17 09:07:36 +08:00

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

lxrmido

2017-07-17 09:10:40 +08:00

无向图的最短路径问题

lights

2017-07-17 09:12:46 +08:00 via iPhone

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

globetour

2017-07-17 09:18:20 +08:00

@qiuyk
@lxrmido
@lights
感谢，

we3613040

2017-07-17 09:27:11 +08:00

又黑我大 php

littleylv

2017-07-17 10:33:17 +08:00

又黑我大 php

orvnge

2017-07-17 11:18:25 +08:00

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

globetour

2017-07-17 11:36:05 +08:00 via Android

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

Shura

2017-07-17 11:38:22 +08:00 via Android

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

iyaozhen

2017-07-17 11:43:24 +08:00 via Android

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

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

globetour

2017-07-17 11:57:44 +08:00 via Android

@Shura 还是兄弟理解我

globetour

2017-07-17 11:58:45 +08:00 via Android

@iyaozhen 好像去不掉了

orvnge

2017-07-17 14:45:46 +08:00

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

globetour

2017-07-17 14:56:29 +08:00 via Android

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

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

cxbig

2017-07-17 15:16:25 +08:00 via iPhone

试试 Neo4j ？

globetour

2017-07-17 15:23:38 +08:00 via Android

@cxbig 图形数据库？

cxbig

2017-07-17 15:31:56 +08:00 via iPhone

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

globetour

2017-07-17 15:35:47 +08:00 via Android

@cxbig 学习了

murusu

2017-07-17 15:40:08 +08:00

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

globetour

2017-07-17 15:41:29 +08:00 via Android

@murusu 你 q 多少，加一下

solaro

2017-07-17 17:42:32 +08:00

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

globetour

2017-07-17 17:44:52 +08:00 via Android

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

liuhaotian

2017-07-17 17:48:40 +08:00 via iPhone

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

globetour

2017-07-17 18:18:08 +08:00 via Android

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

stone1342006

2017-07-17 19:34:59 +08:00

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

globetour

2017-07-17 20:06:32 +08:00 via Android

@stone1342006 容我消化一下