查看: 2960|回复: 6

[问题求助] 最短路问题

字体大小: 正常放大

小累

2 主题	13 听众	151 积分

升级 25.5%

TA的每日心情

	奋斗 2016-5-23 09:05

签到天数: 45 天

[LV.5]常住居民I

自我介绍: 啊呀呀呀呀哎呀呀

电梯直达

1^#

发表于 2014-5-6 22:08 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

赋权图问题。遇到一种问题，图中节点及边均被赋权，求解图中两个节点（比如源点到汇点之间）的最短路径。我的疑问是：节点上的权值要怎么处理呢？比如能够通过一种方式等效到邻边上或者其他方法。查了好多文献都没找到这种问题的解决方法，着急得都快分分钟去自挂东南枝了。有人能指点迷津吗？跪谢！！！

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

小累

2 主题	13 听众	151 积分

升级 25.5%

TA的每日心情

	奋斗 2016-5-23 09:05

签到天数: 45 天

[LV.5]常住居民I

自我介绍: 啊呀呀呀呀哎呀呀

2^#

发表于 2014-5-7 08:28 |只看该作者 |招呼Ta 关注Ta

为什么没有人指点一下啊啊啊啊啊啊，要自挂东南枝了啊

我也说一句

发表

使用道具举报

guozihu1986

2 主题	13 听众	155 积分

升级 27.5%

TA的每日心情

	怒 2014-12-14 20:39

签到天数: 37 天

[LV.5]常住居民I

3^#

发表于 2014-5-16 09:11 |只看该作者 |招呼Ta 关注Ta

我觉得楼主要先想清楚结点的权重对于计算最短路径会产生什么样的影响，是正面还是负面的，可不可以考虑把每个结点的权重分配给与之相连的边，然后再计算最短路。比如某个点的权重为10，有5条边与之相连，是否可以考虑按照边的权重将10分配给这5条边。另外，边的权重越大应该得到的来自周围点的权重是越多还是越少呢，需要楼主自己考虑。只是看了楼主的帖子觉得很有意思，所以把自己的想法写一下，不一定有道理。