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

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

  •  
  •   globetour · 125 天前用 Android 发布 · 2107 次点击
    这是一个创建于 125 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    就是说用户 a 与 d 之间找到一个最短的路径算法。
        20
    cxbig   125 天前 via iPhone
    试试 Neo4j ?
        21
    globetour   125 天前 via Android
    @cxbig 图形数据库?
        22
    cxbig   125 天前 via iPhone
    @globetour 对,擅长处理 object 之间的关系。
        23
    globetour   125 天前 via Android
    @cxbig 学习了
        24
    murusu   125 天前
    最近也在找相关资料,估计楼主跟我在弄的东西有点类似
        25
    globetour   125 天前 via Android
    @murusu 你 q 多少,加一下
        26
    solaro   125 天前
    猜测楼主在脉脉之类的公司
        27
    globetour   125 天前 via Android
    @solaro 个人瞎搞,真的,这个对于大公司应该不难搞吧
        28
    liuhaotian   125 天前 via iPhone
    这种关系图应该是稀疏图吧
    Dijkstra 够了
        29
    globetour   125 天前 via Android
    @liuhaotian 我看 Dijkstra 都是用于算节点之间的具体数值的距离,没看到怎么去算两个人之间最短关系路径的例子呢,比如没办法量化每个节点与公司之间的数值啊!
        30
    stone1342006   125 天前
    @globetour 初始化所有人之间都是无穷远, 曾经有过共同工作经历的可以加一条长度为 1 的边啊,就阔以初始化这个图了
        31
    globetour   125 天前 via Android
    @stone1342006 容我消化一下
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   1779 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.0 · 67ms · UTC 12:15 · PVG 20:15 · LAX 04:15 · JFK 07:15
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1