zuizhenxt 2016-03-05 06:51 采纳率: 0%
浏览 1690
已结题

有限制的遍历问题，dijkstra算法是否最简

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

  • 写回答

1条回答 默认 最新

  • u52983610 2016-03-05 07:19
    关注

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

    评论

报告相同问题？

悬赏问题

  • ¥15 如何在scanpy上做差异基因和通路富集？
  • ¥20 关于#硬件工程#的问题，请各位专家解答！
  • ¥15 关于#matlab#的问题：期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707，使系统具有较小的超调量
  • ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
  • ¥30 截图中的mathematics程序转换成matlab
  • ¥15 动力学代码报错，维度不匹配
  • ¥15 Power query添加列问题
  • ¥50 Kubernetes&Fission&Eleasticsearch
  • ¥15 報錯：Person is not mapped，如何解決？
  • ¥15 c++头文件不能识别CDialog