2 zuizhenxt zuizhenxt 于 2016.03.05 14:51 提问

有限制的遍历问题,dijkstra算法是否最简 5C

近期在做一个编程作业。
有一带权重的有向图,给定起点B,终点E,以及n个必须经过的点,通过编程算出权重最小的点。
因为希望计算最简,所以在通过dijkstra算法遍及,再排除不经过n个必须经历点的情况之后,在思考:是否有更为简便的算法,或者有一两个可以大剪枝的方面,用来保证一些情况不需要进入大循环?
望指教!

1个回答

u013596119
u013596119   Rxr 2016.03.05 15:19

可以对b,e还有n个点都进行dijkstra,构造一个新的图包含b,e和n个点,权重就是某点到某点的最短路径,然后对新图用dijkstra

zuizhenxt
zuizhenxt 回复DarthHaric: 很感谢!
接近 2 年之前 回复
zuizhenxt
zuizhenxt 回复DarthHaric: 要不加qq我给你发图吧?我qq是2779881250
接近 2 年之前 回复
u013596119
u013596119 回复zuizhenxt: 原题是什么?我的算法是错的。。。我的算法最后变np了
接近 2 年之前 回复
zuizhenxt
zuizhenxt n个点是必须被包括,可是这样不一定会有路径到达终点。还有一些不一定要被包括的点也需要被算在内吧?
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!