数学建模社区-数学中国

标题: 最短路问题 [打印本页]

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

作者: 小累 时间: 2014-5-7 08:28
为什么没有人指点一下啊啊啊啊啊啊，要自挂东南枝了啊

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

作者: gaoshuzeng 时间: 2014-5-16 14:10
楼主问题描述不清楚，最好完整的问题贴出来看看!

作者: 小累 时间: 2014-5-17 22:17

guozihu1986 发表于 2014-5-16 09:11
h% t7 u" J0 j Q- F! Z% U t我觉得楼主要先想清楚结点的权重对于计算最短路径会产生什么样的影响，是正面还是负面的，可不可以考虑把每 ...

谢谢！我目前主要的问题正如你上所述，如果将节点权重分配到边上，那么是怎么等效呢？没有能够参考的相关原则。

作者: guozihu1986 时间: 2014-5-18 07:38

小累发表于 2014-5-17 22:17 4 n9 h. ?9 u T) x. i1 J* `' ]+ K$ j
谢谢！我目前主要的问题正如你上所述，如果将节点权重分配到边上，那么是怎么等效呢？没有能够参考的相关 ...

不知道楼主有没有实际的问题背景，这样直接说还真是很难说清，最好根据实际问题背景来确定分配原则

作者: 滴水无痕 时间: 2014-5-23 16:52
。。。。。。。。。。。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)