用dijkstra算法求解最短路径,

whitestone882022-10-04 11:39:541条回答

用dijkstra算法求解最短路径,
point/1..86/:v;
road(point,point):w,x;
endsets
data:
数据
enddata
@for(road(i,j):w(i,j)=0);
w(5,13)=9.05; w(5,39)=8.93; w(5,33)=12.28; w(5,55)=8.37; w(5,74)=12.51;w(7,33)=0.65; w(7,66)=1; w(8,38)=2; w(8,67)=3.87; w(9,44)=2.83; w(9,69)=9.04; w(10,71)=0.29;
w(11,72)=17.2; w(14,77)=1.54;w(15,78)=17.65;w(16,59)=6.95;w(17,24)=2.76; w(17,33)=14.76; w(17,60)=1.43; w(17,59)=6.15; w(18,81)=11.97;w(19,85)=6.89;w(20,83)=13.55;
w(21,23)=7.3; w(21,57)=9.45; w(21,65)=11.51; w(22,65)=3.4; w(22,81)=3.4;w(23,61)=1.73; w(23,66)=11.51;w(24,26)=1.89; w(24,27)=3.09; w(24,28)=4.56; w(25,26)=1.03;
w(25,27)=2.23; w(25,27)=3.7; w(26,65)=5.24; w(27,65)=6.44; w(27,86)=6.44;w(28,29)=194.55; w(28,36)=107.08; w(28,37)=107.55; w(28,38)=173.12; w(28,65)=7.9;
w(29,31)=2.79; w(29,32)=10.7; w(29,33)=14.9; w(29,66)=14.9;
w(30,31)=1.56; w(30,32)=9.47; w(30,33)=13.31; w(30,66)=13.67; w(30,68)=17.85; w(31,78)=13.42;
w(32,59)=5.69;w(34,36)=101.33; w(34,37)=101.79; w(34,38)=167.37; w(34,85)=7.9;w(35,38)=47.53; w(35,85)=7.9; w(36,52)=0.25;w(37,42)=9.43;w(37,43)=9.83;
w(37,69)=10.07;w(38,39)=1.72;w(38,40)=1.12;w(38,70)=9.65;w(39,67)=3.59;w(40,67)=2.99;w(40,77)=2.99;w(41,68)=1.05;w(42,48)=9.59;w(42,68)=10.88;w(42,73)=9.73;
w(43,68)=11.29;w(44,47)=1.98;w(44,70)=13.69;w(45,53)=18.3;w(45,70)=8.96;w(45,72)=20.49;w(46,69)=1.97;w(46,78)=19.61;w(47,69)=8.18;w(47,78)=18.01;w(48,51)=15.65;
w(48,71)=20.6;w(49,51)=3.03;w(49,71)=7.98;w(49,78)=19.2;w(50,71)=1.8;
w(50,78)=18.39;w(51,73)=15.79;w(52,53)=7.69;w(52,64)=0.7;w(52,72)=9.87;w(53,71)=18.86;
w(54,56)=9.28;w(54,72)=13.1;w(54,74)=13.1;w(55,58)=12.22;w(55,76)=17.18;w(56,75)=11.88;w(56,78)=17.76;w(57,78)=7.78;w(57,79)=14.54;w(58,59)=9.24;
w(58,77)=16.36;w(59,79)=9.89;w(60,82)=2.01;w(61,82)=5.93;w(61,83)=5.93;w(62,83)=12.04;w(62,85)=3.67;w(63,84)=8.96;w(63,86)=6.75;w(64,85)=6.54;
w(65,66)=15.71;w(67,68)=19.89;w(67,70)=11.53;w(68,69)=11.53; w(69,70)=19.89; w(71,72)=21.05; w(71,73)=21.05;
w(72,73)=15.71;w(74,75)=15.71;w(76,78)=21.05;w(76,77)=21.05;w(77,78)=21.05;w(80,81)=12.12;w(83,84)=15.71;w(85,86)=15.71;
min=@sum(road(i,j):w(i,j)*x(i,j)+v(j)*x(i,j));
@for(point(i)|i#ne#1#and#i#ne#2:@sum(point(k):x(k,i))=@sum(point(j):x(i,j)));
@sum(point(j):j#ne#1:x(1,j))=1;
@sum(point(k)|k#ne#1:x(k,1))=0;
@sum(point(k)|k#ne#11:x(k,2))=1;
@sum(point(j)|j#ne#11:x(11,j))=0;
@for(road(i,j):x(i,j)

已提交,审核后显示!提交回复

共1条回复
胜男零 共回答了12个问题 | 采纳率91.7%
改过了 没有可行解 自己找我看哪里有问题
1年前

相关推荐

试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态.
升斗ee1年前1
suyuanguan 共回答了27个问题 | 采纳率81.5%
1 c:2
2 c:2 f:6
3 c:2 f:6 e:10
4 c:2 f:6 e:10 d:11
5 c:2 f:6 e:10 d:11 g:14
6 c:2 f:6 e:10 d:11 g:14 b:15
数据结构,最短路径在图中,采用dijkstra算法求出图的最短路径,那这个最短路径是否就是图的最小生成树呢,望能给出详细
数据结构,最短路径
在图中,采用dijkstra算法求出图的最短路径,那这个最短路径是否就是图的最小生成树呢,望能给出详细解答,谢谢
雅倩啊切1年前1
OINANA38 共回答了33个问题 | 采纳率90.9%
采用dijkstra算法求出图的最短路径,这个最短路径不是图的最小生成树.当然在某个特殊的情况,可能从一个顶点出发到某个顶点的最短路径与图的最小生成树所经过的顶点边相同.
最小生成树的要求包含所有n顶点!
C初学者求助一道课本原题(Dijkstra算法)
C初学者求助一道课本原题(Dijkstra算法)
void ShortestPath_DIJ(Mgraph G,int v0,PathMatrix &P,ShortPathTable &D){
//求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][w]为TRUE,则w是从v0到v当前求的最短路径上的顶点
//final[v]为TRUE当且仅当v在S中,即已经求得从v0到v的最短路径
for (v=0; v
yuhui69821年前1
283594397 共回答了8个问题 | 采纳率87.5%
我也是初学者.不过大概看到懂:
1、D[w] = min + G.arcs[v][w];P[w] = P[v]; P[w][w] = TRUE; //P[w] = P[v] + P[w]
这句话就是传说中最短路径的“松弛”技术.(这个不懂没关系)
2、确实的,最短路径这种算法,就算你看懂了也没用,最主要是要去OJ上实践一下,才能够真正懂得算法的奥妙.
3、给你推荐几道最最简单的Dijkstra算法应用题吧:
ZOJ上的1221题;
POJ上的1258题;
ZOJ上的1406题;(这些题都是很经典的)
4、下面是我自己理解后给你写的Dijkstra算法,你的写法不好懂,我的比较清晰:
void Dijkstra()
{
int q,w;
for(q=1;q
Dijkstra算法与Floyd算法的比较问题
Dijkstra算法与Floyd算法的比较问题
Dijkstra算法的复杂度为,Floyd算法的复杂度为,如果采用Dijkstra算法来计算图中任两点之间的最短距离,与Floyd算法相同,是否说明此时没有必要采用Floyd算法?
枫叶8881年前1
wbb111555 共回答了17个问题 | 采纳率94.1%
有必要,因为
1、如果依次对某个顶点运用Dijkstra算法,则与Floyd算法相比,很多路径和结果计算是重复的,虽然复杂度相同,但是运算量差了很多;
2、更为重要的是:Dijkstra算法使用的前提是图中路径长度必须大于等于0;
但是Floyd算法则仅仅要求没有总和小于0的环路就可以了
因此Floyd 算法应用范围比Dijkstra算法要广.
dijkstra算法是深度优先还是广度优先?
绿色玻璃心20061年前1
hi_coco123 共回答了18个问题 | 采纳率94.4%
广度优先
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.
用DIjkstra算法找最短路径, 如下图
用DIjkstra算法找最短路径, 如下图

最先找到节点应该是?AEBCDF

在知道B后,可以到C和D, 最短路径都是6 为什么是选择C作为节点。


adsan1年前1
水草飞灰 共回答了24个问题 | 采纳率91.7%
因为程序中是默认从A到F的顺序扫描的……其实D也是可以的……这里具体看你的算法实现过程……
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
舍得亦或舍不得1年前1
taoism 共回答了19个问题 | 采纳率89.5%
初始化d[i]为无穷大,由于从v4开始,所以将d4=0,标记v4已选择.
下面开始Dijkstra算法:
和v4相连的且未标记的点有v2和v6,这样更新d2=20,d6=15,选择未标记所有点中最小的d6=15,标记v6已选择,这样我们算出了v4->v6最短距离d6=15;
从v6开始,和v6相连的且未标记的是v2,此时算d6+6=21>20,所以不更新d2,选择未标记所有点中最小的d2=20,标记v2已选择,这样算出了v4->v2最短距离d2=20;
从v2开始,和v2相连的且未标记的有v1和v5,d1=d2+10=30,d5=d2+30=50,选择未标记所有点中最小的d1=30,标记v1已选择,这样我们算出了v4->v1最短距离d1=30;
从v1开始,和v1相连的且未标记的有v3,d3=d1+15=45,选择剩下没被选的所有点的最小的d3=45(d5=50),标记v3已选择,这样我们算出了v4->v3最短距离d3=45
从v3开始,没有出去的路径,不更新距离,选择剩下没被选的所有点的最小的d5=50,标记v5已选择,这样我们算出了v4->v5最短距离d5=50.
此时所有的点都被访问,结束.
注:上面的标记点已选择注意下,在算法的实现中用的是将所有的点放入队列中,一旦一个点被选择就是说求出了最短距离,就从此队列删除该点,一直到此队列为空,结束算法,我写标记只是为了方便理解.
希望能帮你清晰了解Dijkstra算法,图论中很重要的算法之一.
弗洛伊德算法Floyd和迪杰斯特拉Dijkstra算法
弗洛伊德算法Floyd和迪杰斯特拉Dijkstra算法
一个三维求多源,一个二维求单源,这我明白.我现在想用下面的二维实现单源:for(i=1;i
黄翰林1年前1
qwwq 共回答了14个问题 | 采纳率92.9%
4条路径 4个顶点编号为1,2,3,4
1-->4 1
4-->3 3
4-->2 1
2-->3 1
(后面为路段长度)
djkstra 是从已经确定较短路径的点出发扩展.
求Dijkstra算法,计算网络最短路径
求Dijkstra算法,计算网络最短路径
希望有详细说明,有典型例题
石小瑜1年前1
随风而逝720 共回答了15个问题 | 采纳率86.7%
算法导论上有比较清晰的讲解
dijkstra算法与floyd算法有什么区别?是不是dijkstra算法是求一个点到另一个点的最短路径,而floyd算
dijkstra算法与floyd算法有什么区别?是不是dijkstra算法是求一个点到另一个点的最短路径,而floyd算法是求一个点到所有点的和最短路径?
tiantian07331年前1
浅蓝色的爱_静 共回答了11个问题 | 采纳率90.9%
Dijkstra 算法 在网络中用得多,一个一个节点添加,加一个点刷一次路由表.
Floyd 算法 :把所有已经连接的路径都标出来,再通过不等式比较来更改路径.
实现过程不太相同.前一个是用在大网络中,对节点数目和具体连接不了解时候使用,后面是总体把握了,再对各连接具体路径进行修正.
dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
AFF25521年前2
80249711 共回答了22个问题 | 采纳率100%
楼上正解,你找个图自己用此算法实践一下就知道了,从A点出发,发现离A最近的点是B点,那么我们就已经认为A到B的最短距离就是AB了,如果有负数,就指不定冒出个C点,AC+CB
对于同一个邻接矩阵,用floyd与dijkstra算法解出不同的结果
风中的泪儿1年前2
seeking_U 共回答了20个问题 | 采纳率100%
估计是你的程序有错误的地方,我求出来是一样的
dijkstra算法 最短路径问题
dijkstra算法 最短路径问题
话说dijkstra算法可以求解一个节点到其他各节点的最短路径,但是如果节点间存在多条等长的最短路径怎么对这个算法修改呢?不要floyd算法或者别的算法,就dijkstra算法.
ls5885881年前1
woaimmzhou 共回答了17个问题 | 采纳率94.1%
迪杰斯特拉算法在程序中对路径的权值相等时进行判断,根据条件进行保存特定的路径,要不你就把所有权值相等的路径都保存下来,最后再根据你的条件进行保留.如:用一个List来保存相同路径设A-B的最小权值为MinWeight,当前路径的权值为Weight,在进行路径计算时会有这样的判断,if(MinWeight>Weight){MinWeight=Weight,修改原有路径.},你可以再加一个判断,if(MinWeight==Weight){MinWeight=Weight,在List中Add这条新路径},这个List可以在节点的Class中定义
有向图中,权值的范围为0到常数W的整数,给定源点s,修改Dijkstra算法,使最短路的时间复杂度为O(WV+E)
不添了1年前1
52113145211314 共回答了10个问题 | 采纳率100%
如何做Dijkstra也要比O(WV+E)好吧
一个偏堆实现的Dijkstra都是O(VlogV+E)吧
一个带有懒操作的基数堆实现的Dijkstra的额外空间复杂度O(Klog),时间复杂度是O(Vlog + E)
令k = W,而且不必带有懒操作,只需额外花费O(W)的空间,即可取得O(V+E)的复杂度
Floyd算法与Dijkstra算法的不同
asdf963asdf1年前1
mkleelee 共回答了20个问题 | 采纳率100%
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法.
算法过程:1,从任意一条单边路径开始.所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连.

2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短.如果是更新它.
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.
 
算法步骤如下:

  1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值

  若存在,d(V0,Vi)为弧上的权值

  若不存在,d(V0,Vi)为∝

  2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S

  3. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的

  距离值比不加W的路径要短,则修改此距离值

  重复上述步骤2、3,直到S中包含所有顶点,即S=T为止
最短路径的Dijkstra算法思路
沧海一头猪1年前1
云筱阁主 共回答了20个问题 | 采纳率100%
百度就有,你也没说什么语言,就不细说了,数据结构知道吧,无论是C的还是JAVA的把这个当做重点来讲,当然还有部分算法设计的书也有,借本书看看就明白了,我的曾经是用MAP实现的
试用Dijkstra算法求从v1到其余各顶点的最短路径,写出每一步的状态.算法我会,主要是步奏!下图为题目图,还有就是谁
试用Dijkstra算法求从v1到其余各顶点的最短路径,写出每一步的状态.算法我会,主要是步奏!下图为题目图,还有就是谁有2013南京航空航天大学829试卷的答案啊?
igd9e1年前1
平风造雨四无君 共回答了10个问题 | 采纳率100%


Kruskal 算法与Dijkstra算法区别
马小猫1年前3
我是henry 共回答了21个问题 | 采纳率90.5%
Kruskal是最小生成树算法,Dijkstra是最短路径算法,有本质上的区别.
问一下为什么dijkstra算法不能处理负权边.最好举例说明啊,越仔细越好...
lolitacao1年前1
dwhro 共回答了24个问题 | 采纳率95.8%
会形成环,使得路越走越短,到不了终点.