应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » MATLAB/Mathematica » 两点间所有路径的算法，并且求出各情况路径的大小
51/1返回列表
查看: 2236  |  回复: 5
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

木之枝

铜虫 (小有名气)

[求助] 两点间所有路径的算法，并且求出各情况路径的大小

各点 的 距离矩阵 已知，依据《图论算法及其MATLAB实现》可求得两点间 最短路径 经过的点及其大小。
现在想求两点之间 存在的所有路径，并得到各路径的大小。

如附件中所示，点1到点7的所有路径和路径长度大小。各点之间的距离已知。
两点间所有路径的算法，并且求出各情况路径的大小
1000201.png
回复此楼

» 收录本帖的淘帖专辑推荐

BE A GOOD SCHOLAR

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2013-10-21 10:13:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

木之枝

铜虫 (小有名气)
引用回帖:
2楼: Originally posted by 锐利的碎片 at 2013-10-21 10:29:51
用dfs就可以了
比如这个：
def find_all_paths(graph, start, end, path=[]):
        path = path +
        if start == end:
            return
        if not graph.has_key(start):
            re ...

因为我对MATLAB不熟，之前求最短路径是从图论书上直接查的程序存为.m文件，然后在命令窗口直接输入邻接矩阵，再输入.m文件里的函数，就得到结果了。

还想请问一下，你编的程序里面 path=[]、  return [] 的括号里需要写什么吗？ 我把你的程序也存为.m文件了，但不知道怎么用啊。望解答一下，非常感谢！！！
赞一下 回复此楼
3楼2013-10-21 15:31:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 6 个回答

锐利的碎片

木虫 (正式写手)

star watcher

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与，应助指数 +1
木之枝: 金币+30, ★★★★★最佳答案, 谢谢虫友把程序写出来！非常感谢！！！ 2013-10-21 15:26:33
用dfs就可以了
比如这个：
def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths
这里图是用邻接表存的，邻接矩阵的话改下就可以了
赞一下 回复此楼
2楼2013-10-21 10:29:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

木之枝

铜虫 (小有名气)
引用回帖:
2楼: Originally posted by 锐利的碎片 at 2013-10-21 10:29:51
用dfs就可以了
比如这个：
def find_all_paths(graph, start, end, path=[]):
        path = path +
        if start == end:
            return
        if not graph.has_key(start):
            re ...

比如各点之间的距离矩阵为
W=[0        1        2        1        2        3;
1        0        1        1        1.414        2;
2        1        0        1.414        1        1;
1        1        1.414        0        1        2;
2        1.414        1        1        0        1;
3        2        1        2        1        0];
为邻接矩阵。
怎么求点1到点6的所有路径啊？
把上面一条边 简化为 点1，下面一条边 简化为 点6.
两点间所有路径的算法，并且求出各情况路径的大小-1
无标题.png
赞一下 回复此楼
4楼2013-10-21 16:15:05
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

锐利的碎片

木虫 (正式写手)

star watcher

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
木之枝: 金币+10, ★★★很有帮助, 谢谢！ 2013-10-22 11:05:26
引用回帖:
3楼: Originally posted by 木之枝 at 2013-10-21 15:31:15
因为我对MATLAB不熟，之前求最短路径是从图论书上直接查的程序存为.m文件，然后在命令窗口直接输入邻接矩阵，再输入.m文件里的函数，就得到结果了。

还想请问一下，你编的程序里面 path=[]、  return [] 的括号 ...

这个是python写的。matlab太久不用，已经忘完了。
这是我写的用python的Networkx库计算的例子：
http://nbviewer.ipython.org/7084321
不是研究算法就直接用现成的。
赞一下 回复此楼
5楼2013-10-21 22:07:32
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 6 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考博] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +4 k0dTPqJtl0jt 2026-08-14 5/250 2026-08-15 04:45 by 4wMiSEwB6436
[找工作] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +4 k0dTPqJtl0jt 2026-08-14 4/200 2026-08-15 02:21 by 4wMiSEwB6436
[考研] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +3 HFw0lei2R37i 2026-08-14 7/350 2026-08-15 00:40 by 4wMiSEwB6436
[考研] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +4 HFw0lei2R37i 2026-08-14 8/400 2026-08-15 00:16 by 4wMiSEwB6436
[教师之家] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 HFw0lei2R37i 2026-08-14 5/250 2026-08-14 22:32 by 4wMiSEwB6436
[基金申请] filecode +6 cratir 2026-08-14 10/500 2026-08-14 18:29 by 笑叹辞穷
[基金申请] 奇怪，两个人的filecode固定段从头到尾一模一样 +8 布布和一二 2026-08-10 11/550 2026-08-14 14:58 by Equinoxhua
[基金申请] 应该是93bebmhtak前后十一个字符比较关键 +23 Lanmanbaby 2026-08-09 37/1850 2026-08-14 13:40 by Equinoxhua
[硕博家园] 请教兼职经验 +3 是阿文鸭 2026-08-09 3/150 2026-08-14 12:07 by HER12025
[硕博家园] 读博的好处 +4 lnee 2026-08-11 4/200 2026-08-14 10:20 by ahsoarli
[基金申请] filecode +15 documentary 2026-08-10 17/850 2026-08-14 10:08 by kissu88
[基金申请] 我的国基提前知道中了，可是同事的操作让我实在接受不了，怎么会有这样的人 +10 家与远方 2026-08-10 15/750 2026-08-14 02:08 by 绵羊哥哥
[基金申请] 关于Filecode分析方法 +9 majunge000 2026-08-10 12/600 2026-08-13 23:20 by iwuli
[文学芳草园] 阿姨 +4 汪汪锅 2026-08-09 4/200 2026-08-13 19:43 by arzu_hma
[硕博家园] 一作与独作在应聘高校教师时区别大吗 +3 mbygzh 2026-08-08 4/200 2026-08-13 19:31 by 龙-樱
[基金申请] 重要来源：本周末出结果 +10 瞬息宇宙 2026-08-12 10/500 2026-08-13 15:46 by likettle
[基金申请] 分享一下我之前已中青C的计划书的filecode +4 布布和一二 2026-08-11 5/250 2026-08-13 12:56 by cratir
[基金申请] 结合人工智能，周易传统文化，filecode打分制来了，3分以上希望很大。 +3 Tide man 2026-08-12 4/200 2026-08-13 08:35 by ZJTJZ
[基金申请] 2019年青年基金涵评意见，大家看看几个A，几个B? +11 Tide man 2026-08-11 11/550 2026-08-13 07:35 by 撸猫猫
[基金申请] 2026国自然放榜时间 +9 布布和一二 2026-08-08 9/450 2026-08-10 11:22 by xxxx2020
信息提示
关闭
请填处理意见
关闭