通訊網理論基礎實驗報告
實驗二：端間最短路徑演算法的**實現
27班項明鈞2013210731
27班唐睿2013210742
一、實驗目的
通訊網路中為傳輸資訊，需要求解網路中端點之間的最短距離和路由。此時網路可以用圖來表示，每條邊的權可為該邊的距離、成本或容量等物理意義。端間最短徑問題主要分為兩種情況：
尋找指定端至任意其它端之間的最短距離和路由，可以使用dijkstra演算法解決；尋找任意兩端之間的最短距離和路由, 使用floyd演算法解決。
dijkstra演算法為標號置定法，通過依次置定指定端與當前端的最短距離和回溯路由來實現；floyd演算法為標號修正法，通過初始化圖的距離矩陣和路由矩陣、並在迭代過程中不斷重新整理最短距離和路由資訊，直至演算法結束才能求出任意兩點間的最短距離矩陣和前向（或反向）路由矩陣。
本次實驗要求利用matlab分別實現dijkstra演算法和floyd演算法，針對輸入的鄰接距離矩陣，計算圖中任意兩點間的最短距離矩陣和路由矩陣，且能查詢任意兩點間的最短距離和路由。
二、實驗原理
2.1 dijkstra演算法描述如下：
d演算法的每個端點的標號為，其中表示到的距離，而為端點是到最短路徑的最後乙個端點。
圖的每一邊上有乙個權。
d0：初始，記，設的標號為。
d1：對任一邊，計算的值。在中選一邊，設為。使，並令，並且的標號為。
d2：當出現下面情況之一時停止。
1）；2）但
2.2 floyd演算法可描述如下：
給定圖及其邊的權
f0：初始化距離矩陣和路由矩陣。其中：
f1：對於已求得的和，依據下面的迭代求解和。
f2：若，重複f1；若，終止。
三、實驗內容
採用的語言：matlab
資料結構：基本矩陣計算，基本陣列計算
主要函式：
dijkstra演算法：
1、初始化path矩陣
path=zeros(n,n);
for i=1:n
for j=1:n
if d(i,j)~=100
path(i,j)=i;
endendend2、各點最短距離矩陣生成
for i=1:num
x=al(i);
for j=1:n
newdistance(i,j)=distance(x)+a(x,j);
endend3、比較所有點得出乙個最短距離並生成距離矩陣d
for i=1:n
if (newdistance(1,i)y=newdistance(1,i);
u(1,1)=i;
endend d(s,u(1,1))=y;
4、生成回溯路由矩陣path
for i=2:num
if (newdistance(i,u(1,1))==newdistance(1,u(1,1)))
r(1,1)=al(i);
endendif (r(1,1)==0)
r(1,1)=al(1);
endpath(s,u(1,1))=r(1,1);
5、生成兩點之間的具體路由陣列
luyou=zeros(1,n);
luyou(n)=o;
h=d(l,o);
for m=2:n
if (path(l,o)~=l)
luyou(n-m+1)=path(l,o);
o=path(l,o);
else
luyou(n-m+1)=l;
endendfloyd演算法：
1、初始化path矩陣
path=zeros(n,n);
for i=1:n
for j=1:n
if d(i,j)~=100
path(i,j)=i;
endendend2、同時生成距離矩陣和路由矩陣
for k=1:n
for i=1:n
for j=1:n
if (d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);
path(i,j)=path(i,k)
end end
endend3、生成兩點之間的具體路由陣列
luyou=zeros(1,n);
luyou(1)=s;
h=d(s,t);
for m=2:n
if (path(s,t)~=t)
luyou(m)=path(s,t);
s=path(s,t);
else
luyou(m)=t;
endend4、輸出函式
disp(d);
disp(path);
disp(h);
disp(luyou);
演算法流程圖：
dijkstra
floyd：
4、實驗資料與結論分析
dijkstra
圖一：鄰接矩陣
最短路徑距離矩陣：
回溯路由矩陣：
端點對v4和v6距離和路由
端點對v3和v4距離和路由
圖二：鄰接矩陣
最短路徑距離矩陣
回溯路由矩陣
端點對v1和v7
v3和v5
v1和v6
自定義圖：
鄰接矩陣
最短路徑距離矩陣
北郵通訊原理實驗報告
北京郵電大學 學院 資訊與通訊工程學院 班級 姓名 姓名 1 了解dsb sc am訊號的產生以及相干解調的原理和實現方法。2 了解dsb sc am訊號波形以及振幅頻譜特點,並掌握其測量方法。3 了解在傳送dsb sc am訊號加導頻分量的條件下,收端用鎖相環提取載波的原理及其實現方法。4 掌握鎖...
北郵移動通訊技術實驗報告
班級姓名 學號班內序號 這是我們第一次走出校園進行專業課實驗，來到了位於海淀區的大唐電信科技股份 公司的大樓前花團錦簇，更加襯托出大唐的輝煌業績。我想大家心中，都有一種由衷的嚮往之情。進入公司內部，我感受到了濃厚的工作氛圍，實驗室裡還有幾個埋頭工作的人，對著電腦偶爾相互討論交流。而我們有序地在電腦前...
計算機通訊網實驗總結
一學期的計算機網路實驗課終於要結束了。通過這一學期的學習使得自己在計算機網路這一方面有了更多的了解，更深刻的體會，對計算機網路也有了更多的興趣。大家在一起對計算機基礎教學中 培訓的一些問題進行了 相互間受到許多啟發。特別是每一次實驗課，因為實驗的要求，老師要求我們提前自行組建好團隊，以團隊為基礎進行...