2 dgghjnjk dgghjnjk 于 2016.03.06 10:55 提问

有一个算法问题,与图论有关

给定一个有向无环权重图G(V,E),V的一个子集为V',从给定的点s出发到给定的点t,找出一条能遍历V'的最短路径,已知权重为1到20的整数。

4个回答

dgghjnjk
dgghjnjk   2016.03.06 10:56

求思路啊!图片说明图片说明图片说明图片说明图片说明

u013596119
u013596119   Rxr 2016.03.06 11:06

昨天刚和问答的一个朋友讨论过

 有一带权重的有向图,给定起点B,终点E,以及n个必须经过的点,通过编程算出权重最小的点。

他的问题是np。。。。
但是你的貌似不是,因为你的G确定不包含环,![图片说明](http://img.ask.csdn.net/upload/201603/06/1457233379_894907.jpg)图片说明

这是我写的算法,用dfs遍历所有s到t的路径,选出路过v‘的比较,

还有一个算法,用floyd计算v'中所有点两两的最短距离,然后全排列,然后在看s,t,这个算法在v’数量较小的情况可以实现,但是v‘数量太大就要越界了

u013596119
u013596119   Rxr 2016.03.06 11:06

还有一张图。。。图片说明

Techay
Techay   2016.03.06 11:39

这不是华为的题吗,这样不好吧

dgghjnjk
dgghjnjk 只是想和大家讨论一下,获得更多的思路,并不是来找答案的
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!