V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
globetour
V2EX  ›  程序员

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

  •  
  •   globetour · 2017-07-17 04:24:02 +08:00 via Android · 3930 次点击
    这是一个创建于 2684 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    31 条回复    2017-07-17 20:06:32 +08:00
    ericls
        1
    ericls  
       2017-07-17 04:25:35 +08:00 via iPhone
    看看 graph theory
    shiji
        2
    shiji  
       2017-07-17 05:36:05 +08:00
    这跟 PHP 有直接关系么。。
    xiaopc
        3
    xiaopc  
       2017-07-17 05:50:36 +08:00 via Android
    单源最短路问题,Dijkstra 等算法
    和语言没关系
    globetour
        4
    globetour  
    OP
       2017-07-17 06:18:21 +08:00 via Android
    @ericls 我查查,感谢
    globetour
        5
    globetour  
    OP
       2017-07-17 06:18:48 +08:00 via Android
    @xiaopc 请教兄弟如何解决呢
    qiuyk
        6
    qiuyk  
       2017-07-17 09:07:36 +08:00
    @globetour 搜一下 Dijkstra 应该就够了 你要嫌复杂就 DFS 或者 BFS 呗...
    lxrmido
        7
    lxrmido  
       2017-07-17 09:10:40 +08:00   ❤️ 1
    无向图的最短路径问题
    lights
        8
    lights  
       2017-07-17 09:12:46 +08:00 via iPhone
    图数据库,或者加一个图算法层
    globetour
        9
    globetour  
    OP
       2017-07-17 09:18:20 +08:00
    @qiuyk
    @lxrmido
    @lights
    感谢,
    we3613040
        10
    we3613040  
       2017-07-17 09:27:11 +08:00
    又黑我大 php
    littleylv
        11
    littleylv  
       2017-07-17 10:33:17 +08:00
    又黑我大 php
    orvnge
        12
    orvnge  
       2017-07-17 11:18:25 +08:00
    和语言无关
    判断相似性就可以了 曼哈顿,欧几里得距离,预先相似,皮尔逊算法都可以
    globetour
        13
    globetour  
    OP
       2017-07-17 11:36:05 +08:00 via Android
    @orvnge 专业,没做过这种算法,感觉无从下手啊。
    Shura
        14
    Shura  
       2017-07-17 11:38:22 +08:00 via Android
    楼主是想找个库函数直接就计算出来吗?
    iyaozhen
        15
    iyaozhen  
       2017-07-17 11:43:24 +08:00 via Android
    楼主把标题里的 php 去掉我们还能做朋友。

    你应该说需求,然后再说自己主力开发语言,下面说不定就有人扔 github 链接了
    globetour
        16
    globetour  
    OP
       2017-07-17 11:57:44 +08:00 via Android
    @Shura 还是兄弟理解我
    globetour
        17
    globetour  
    OP
       2017-07-17 11:58:45 +08:00 via Android
    @iyaozhen 好像去不掉了
    orvnge
        18
    orvnge  
       2017-07-17 14:45:46 +08:00
    @globetour 如果是简单判断相似性的话 其实 这几种算法就是 求两点距离很容易理解 代码也很好弄,你可以 搜索看看
    globetour
        19
    globetour  
    OP
       2017-07-17 14:56:29 +08:00 via Android
    @orvnge 不是简单相似,需要这种结果,比如
    用户 a
    同在公司 a 工作
    用户 b
    同在公司 b 工作
    用户 c
    同在公司 c 工作
    用户 d

    就是说用户 a 与 d 之间找到一个最短的路径算法。
    cxbig
        20
    cxbig  
       2017-07-17 15:16:25 +08:00 via iPhone
    试试 Neo4j ?
    globetour
        21
    globetour  
    OP
       2017-07-17 15:23:38 +08:00 via Android
    @cxbig 图形数据库?
    cxbig
        22
    cxbig  
       2017-07-17 15:31:56 +08:00 via iPhone
    @globetour 对,擅长处理 object 之间的关系。
    globetour
        23
    globetour  
    OP
       2017-07-17 15:35:47 +08:00 via Android
    @cxbig 学习了
    murusu
        24
    murusu  
       2017-07-17 15:40:08 +08:00
    最近也在找相关资料,估计楼主跟我在弄的东西有点类似
    globetour
        25
    globetour  
    OP
       2017-07-17 15:41:29 +08:00 via Android
    @murusu 你 q 多少,加一下
    solaro
        26
    solaro  
       2017-07-17 17:42:32 +08:00
    猜测楼主在脉脉之类的公司
    globetour
        27
    globetour  
    OP
       2017-07-17 17:44:52 +08:00 via Android
    @solaro 个人瞎搞,真的,这个对于大公司应该不难搞吧
    liuhaotian
        28
    liuhaotian  
       2017-07-17 17:48:40 +08:00 via iPhone
    这种关系图应该是稀疏图吧
    Dijkstra 够了
    globetour
        29
    globetour  
    OP
       2017-07-17 18:18:08 +08:00 via Android
    @liuhaotian 我看 Dijkstra 都是用于算节点之间的具体数值的距离,没看到怎么去算两个人之间最短关系路径的例子呢,比如没办法量化每个节点与公司之间的数值啊!
    stone1342006
        30
    stone1342006  
       2017-07-17 19:34:59 +08:00
    @globetour 初始化所有人之间都是无穷远, 曾经有过共同工作经历的可以加一条长度为 1 的边啊,就阔以初始化这个图了
    globetour
        31
    globetour  
    OP
       2017-07-17 20:06:32 +08:00 via Android
    @stone1342006 容我消化一下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1055 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 19:27 · PVG 03:27 · LAX 11:27 · JFK 14:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.