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 shape_predictor_68_face_landmarks.dat
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料
  • ¥15 使用R语言marginaleffects包进行边际效应图绘制