计算机网络与通信课程设计的是完成最小代价算法,包括Bellman算法和Dijkstra算法.doc

计算机网络与通信课程设计的是完成最小代价算法,包括Bellman算法和Dijkstra算法.doc实验目的 3
实验要求 3
实验分析 3
Dijkstra算法的流程 3
Dijkstra算法的描述 3
1•变量代表的描述 3
2•算法描述 3
Bellman算法的流程 .….…… 4
1•变量代表的描述 .… 4
..….….… 4
四．运行结果……………………………………………… 5
五．课程设计总结………………………………………… 7
六．源程序代码…………………………………………… 7
七．参考文献……………………………………………… 10
一、 实验目的：
本次课程设计的目的是完成最小代价算法，包括 Bellman算法和Dijkstra 算法。
二、 实验要求：
•整个课程设计的各个环节都要自己动手。
•算法的原理教材上有，请同学仔细去看。
•编写程序，完成最小代价算法。
•对课程设计进行总结，撰写课程设计报告。
三、 实验分析：
Dijkstra 算法的流程
Dijkstra 算法的描述：
变量代表的描述：
N=网络中的顶点集舍
S=源顶点
M=算法中用到的临时顶点集合
W(i,j)=从顶点i到顶点J的链路耗费。若两个顶点之间不直接相连，则 W(i, i)= a ;若两个顶点之间直
接相连，则W(i , j) > 0。
P(n)=从顶点S到顶点N的最小耗费路径的耗费•算法执行过程中是知道的：算法结束时也 就是S到N的最小耗费路径的耗费。
算法描述
算法总共有3个步骤：
初始化
M=S即临时顶点集合中只有源顶点。
P(n)=W(i • j)对所有nzs即，到相邻顶点的初始路径耗费就是链路耗费。
取下个顶点
找到不在M中且到顶点s有最小耗费路径的相邻顶点，把它加入到临时集合 M中；把依附于该顶点和 M中
某顶点构成路径的边也加入到 M中。
更新最小耗费路径
P(n)=min[P(n) , p(x)+W(x,n)]，对所有 x不属于 M
如果第二项小•则从s到N的路径从现在起就是从 S到X再连上X与 N之间的边。
当所有的顶点都加入到 M以后，算法结束。这样，算法要进行 |V|次选代。结束时，每个顶点 x的值P(x)
就是从s到x的最小耗费路径的耗费(长度)。
注意:步骤2和步骤3要重复执行，直至 M=N也就是说，步骤 2和步骤3在重复到网络中所有顶点都已经找到 最终路径为止。
Bellman算法的流程:
Bellman算法的描述：
变量代表的描述；
s=源顶点
w(i,j)=，则 W(i, i)= g，如果2个顶点之间
直接相连，则 W(i . j) > 0。
H=在算法和当前步骤中路径的最大链路数。
P(n)=从顶点S到顶点N的最小耗费路径的耗费•限制条件是路径的链路数不超过 H。
算法描述
算法总共有2个步骤：
初始化：P0(n)= g,对所有s LH(s)=0，对所有 H。
更新：对相继的每个H》0 对每个n^s,计算PH+1(n)=min[ PH(j)+W(j , n)]找到符合最小条件的顶点
j，将n与该前趋顶点相连，删除 n与所有其它前趋顶点的连接，这些连接是在前面的选代中产生的。从 S
到n的路径以J到n的链路结束。
注意：其中步骤2重复执行，直至路径的耗费不再变化为止；

两种最小代价算法收敛结果是否相同? 答：相同。
两种算法实现过程中，各自需要收集的信息是什么？
答：Bellman算法，在步骤2中，在与顶点n有关的计算中要知道n到其所有相邻顶点的链路耗费以及从特定的源 顶点S到这些顶点的路径总耗费。每个顶点要有到网络中所有其它顶的路径及其耗费，并且时时与其直接连接的 相邻顶点交换这些信息 每个顶点都要用Bellman算法步骤2中的表达式来更新其耗费和路径。所需的只是来计
算相邻顶点的信息以及到这些相邻顶点的耗费。
Dijkstra 算法，步骤3中需要每个顶点知道完整的网络拓扑信息，就是说，每个顶点必须知道网络中所有链路 的链路耗费，这样，对这个算法来说，每个顶点要与所有其他顶点交换信息。 Dijkstra算法要求先构造最短通
路树，然后根据最短通路树形成路由表。构造最短通路树的过程耍用整个网络的拓扑信息。
4、运行结果：
网络无向图

c< "D:\UserPat a\Ad>inist r &t orYsl ilflXDelJUEXDLikJt ra- exe
孑入节点数匸6 输入皿”讣 1 陌5药 G5535 4 8 2 &防翦 &SG35 5535 203 65535
6