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

求最短路

  •  
  •   syhsyh9696 · 2015-12-24 09:53:28 +08:00 · 1810 次点击
    这是一个创建于 1492 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我有一个矩阵,里面储存着两个节点之间距离的长度,假设不可达,如何求两点之间的最短路径?
    11 回复  |  直到 2015-12-24 13:50:35 +08:00
    algas
        1
    algas   2015-12-24 10:45:03 +08:00
    假设不可达,是说没有办法从一个节点到另一个节点吗?
    zrp1994
        2
    zrp1994   2015-12-24 11:03:23 +08:00
    分支限界法树搜索求最短旅行商?
    lijun20020229
        3
    lijun20020229   2015-12-24 11:14:41 +08:00
    旅行商是遍历并回到原点,最短路是寻找两点之间的最短路径。
    没看出这个有什么特殊的地方,用常规算法不行么?
    wendellup
        4
    wendellup   2015-12-24 11:28:28 +08:00
    不可达是啥意思
    syhsyh9696
        5
    syhsyh9696   2015-12-24 11:35:39 +08:00
    不可达是不能直接到达
    zrp1994
        6
    zrp1994   2015-12-24 12:36:25 +08:00
    @syhsyh9696 不能到达的节点之间代价设为正无穷,用树搜索很容易就求出来了
    callofmx
        7
    callofmx   2015-12-24 12:42:32 +08:00
    这个感觉很常规啊,dijkstra 算法不行吗
    长度为负数可以用 floyd
    algas
        8
    algas   2015-12-24 13:24:13 +08:00
    根据矩阵,选择距离当前节点为 1 的节点{j},遍历所有{j}选择到目标节点距离最短的节点作为路径上的下一个节点,依次迭代到目标节点。
    h4x3rotab
        9
    h4x3rotab   2015-12-24 13:30:52 +08:00 via iPhone
    那必须是 Dijkstra 和 Floyd 啊,搜索慢死了
    juxingzhutou
        10
    juxingzhutou   2015-12-24 13:40:56 +08:00
    这不就是算法导论里面的单源最短路和两点最短路两章吗,去找找这两章的内容就是了,相当完整,基本涵盖了可能的场景。
    syhsyh9696
        11
    syhsyh9696   2015-12-24 13:50:35 +08:00
    谢谢大家我去翻书
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   740 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 22:52 · PVG 06:52 · LAX 14:52 · JFK 17:52
    ♥ Do have faith in what you're doing.