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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
总结分析一下三种求解最短路问题的算法,dijkstra算法,spfa算法,floyd算法。
说是总结,其实自己也没有学多长时间只是把自己这段时间的一些经验总结下来,用来供后来的初学者涨点经验吧。对于学习算法,个人的理解就是首先要去理解算法的本质,然后想想算法的实现过程,如何用代码去描述这个算法,然后就是去记模板了(对于像我这种初学者来说,这一步其实蛮重要的)。另外说下做最短路问题的一些容易出错的地方。1、要小心重边,就是题目会给你一些边类似于2 4 5,2 4 3;这种边和权值的。2、要
dijkstra最短路径及其输出(数学建模)
高中同学让我求8个菜市场和35个销售点(他们之间还会有15个路口)之间35*8=280个组合分别的最短路径及其输出。 最短路水题,嘿嘿。能用自己学到的知识帮助别人解决问题真是极好的享受。 具体注释可以见代码,写的蛮清楚的。 #include #include #include #include #include using namespace std; #define INF 0x3f3f
[C++]C++ STL Dijkstra算法 存储多条相同最短路径 shortest path
Dijkstra存储多条相同最短路径使用list结构存储多个顶点(预备)完整源码#include <iostream> #include <list> using namespace std;int main() { list<int> larray[100]; larray[0].push_back(0); larray[0].push_back(1); larray
广度优先算法,深度优先算法和DijKstra算法
我们经常会碰到最短路径问题,而最短路径问题的解决方法多种多样,广度优先搜索(BFS),深度优先搜索(DFS)和DijKstra算法貌似都能解决这个问题,这里就简单介绍一下这些算法,分析一下它们的适用范围。
有向图最短路径问题---Dijkstra算法(过程)
有向图最短路径问题---Dijkstra算法(过程)
有权图中的最短路径问题--Dijkstra算法(Java语言实现)
本篇微博主要介绍有权图中的最短路径问题,由于Dijkstra算法是广度优先搜索的改进算法,所以本文先介绍一下普通的bfs算法。 一.BFS算法 说到BFS算法,其实普通的BFS算法有些类似于二叉树中的层次遍历。因此可以用队列实现,具体步骤如下: 1.访问初始结点v,并标记结点v为已访问; 2.结点v入队列 3.当队列为空时,继续执行,否则算法结束(用while循环判别) 4.出队列时,
为什么Dijkstra算法不适用边长为负数的情况
Dijkstra算法,是有向/无向加权图(就是每条边都有长度)中,计算两个点之间最短距离的有效方法,在使用堆排序的情况下,它的时间复杂度为O(Nlog(N+M)),(这里N代表节点数,M代表边数)很接近线性了,还是非常好的。 不过,Dijkstra算法有一个限制,就是它只适用于边长不为负的图。如果一张图里有负数长的边长,那么Dijkstra算法就不适用了。这时候就需要另外的算法了。 为什么不适用呢?其实很容易就可以找到反例。
Dijkstra算法与Prim算法的区别
1: Prim是计算最小生成树的算法,比如为N个村庄修路,怎么修花销最少。 Dijkstra是计算最短路径的算法,比如从a村庄走到其他任意村庄的距离。 2: Prim算法中有一个统计总len的变量,每次都要把到下一点的距离加到len中; Dijkstra算法中却没有,只需要把到下一点的距离加到cls数组中即可; 3: Prim算法的更新操作更新的cls是已
最短路径问题---Dijkstra算法详解
前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法:...
每天学一点算法-Dijkstra算法
有向图非负权最短路径算法,时间复杂度O(n的平方)。