云南大學(xué)軟件學(xué)院計算機(jī)網(wǎng)絡(luò)原理報告8

1、精選文檔實驗八、Link States Algorithm的實現(xiàn)序號： 姓名： _ 學(xué)號： _ 成績 指導(dǎo)老師： 劉宇 劉春花 1實驗?zāi)康模和ㄟ^編程模擬實現(xiàn)LSA.2實驗環(huán)境：VS.net軟件開發(fā)平臺，可以使用任何編程語言。3實驗要求（1）求網(wǎng)絡(luò)中任何兩個結(jié)點之間的最短路徑（網(wǎng)絡(luò)中至少有4個節(jié)點）。（2）得到任何一個節(jié)點上的轉(zhuǎn)發(fā)表。實驗內(nèi)容、拓?fù)浣Y(jié)構(gòu)Initialization: 2 N' = u /*u is source node*/3 for all nodes j /* j is dest node*/4 if j adjacent to u 5 then D(j) = c(u

2、,j) 6 else D(j) = 7 8 Loop 9 find i not in N' such that D(i) is a minimum 10 add i to N' 11 update D(j) for all j adjacent to i and not in N' : 12 D(j) = min( D(j), D(i) + c(i,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to i plus cost from i to j */ 15

3、 until all nodes in N' 程序：#include<stdio.h>#include<stdlib.h>#define INFINITY 10000 /最大距離 #define MAX_NODES 50 /最大節(jié)點數(shù) int distMAX_NODESMAX_NODES; /distij表示從 i 到 j 的距離int pathMAX_NODES;typedef structint vexnum;int vexMAX_NODES;graph;void init_graph(graph *g)int a,x,y=0;g->vexnum =

4、5; for(a =0;a<g->vexnum;a+)g->vexa=a;for(x=0;x<g->vexnum;x+)for(y=0;y<g->vexnum;y+)distxy=INFINITY;dist01 = 7;dist04 = 1;dist10 = 7;dist12 = 1;dist14 = 8;dist21 = 1;dist23 = 2;dist32 = 2;dist34 = 2;dist40 = 1;dist41 = 8;dist43 = 2;void shortest_path(int s, int t,int n) struct st

5、ate int predecessor; /前驅(qū)節(jié)點 int length; /到起始點的距離 int label; stateMAX_NODES; int i,k,min; struct state * p; for(p=&state0; p<&staten; p+) p->predecessor = -1; p->length = INFINITY; p->label = 0; statet.length = 0; statet.label = 1; k = t; /k 是當(dāng)前工作節(jié)點 do for(i=0; i<n; i+) if(distk

6、i!=0 && statei.label=0) if(statek.length+distki<statei.length) statei.length = statek.length+distki; statei.predecessor = k; k=0; min=INFINITY; for(i=0; i<n; i+) if(statei.label=0 && statei.length<min) k=i; min=statei.length; statek.label = 1; while(k!=s); i=0; k=s; do pathi

7、 = k; k = statek.predecessor; printf("<-%d",pathi); i+; while(k>=0); int main()int m;graph g;g.vexnum = 5;init_graph(&g);printf("從A點出發(fā)到其他各點的最短路徑如下所示：n");printf("n注：0->A點;1->B點;2->C點;3->D點;4->E點n");for(m=1;m<g.vexnum;m+)printf("n從編號為0的A點出

8、發(fā)，到編號為%d的結(jié)點的最短路徑為:n",m);shortest_path(g.vexm,g.vex0,g.vexnum);return 0; ABECD718122通過鏈路狀態(tài)算法計算A點到其它各點的cost，最終輸出A的路由表。A的轉(zhuǎn)發(fā)表： B C D E 最短路徑（A,E,D,C,B) (A,E,D,C) (A,E,D) (A,E) 成本值 6 5 3 14實驗分析，回答下列問題（1）給出LSA算法的主要思想。答：首先引入一個輔助變量Di,它表示當(dāng)前所找到的從始點到每個終點的最短路徑的長度，它的初態(tài)為若有弧則為弧的權(quán)值，若無則為無窮大，且U為已經(jīng)找到最短路徑的結(jié)點的集合，首先比

9、較不屬于U集合的結(jié)點到始點的成本，將最小的結(jié)點并入U中，然后以該結(jié)點為橋梁找到始點到其余各終點的新的最短路徑，即若始點到該點的成本與該點到終點的和小于始點到終點的成本，則設(shè)該成本為始點到終點的最短路徑，然后再找出各終點到始點的最短路徑集合的最小值的終點并入集合U，再循環(huán)執(zhí)行上述步驟直到所有結(jié)點都并入U為止。（2）通過圖表算出任何兩個節(jié)點之間的最短路徑，并給出每個節(jié)點上的轉(zhuǎn)發(fā)表。A的轉(zhuǎn)發(fā)表： B C D E 最短路徑（A,E,D,C,B) (A,E,D,C) (A,E,D) (A,E) 成本值 6 5 3 1B的轉(zhuǎn)發(fā)表： A C D E 最短路徑 （B,C,D,E,A) (B,C) (B,C,D) (B,C,D,E) 成本值 6 1 3 5C的轉(zhuǎn)發(fā)表： A B D E 最短路徑 （C,D,E,A) (C,B) (