1、精選文檔實驗八、Link States Algorithm的實現序號： 姓名： _ 學號： _ 成績 指導老師： 劉宇 劉春花 1實驗目的：通過編程模擬實現LSA.2實驗環境：VS.net軟件開發平臺，可以使用任何編程語言。3實驗要求（1）求網絡中任何兩個結點之間的最短路徑（網絡中至少有4個節點）。（2）得到任何一個節點上的轉發表。實驗內容、拓撲結構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 /最大節點數 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; /前驅節點 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 是當前工作節點 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點出發到其他各點的最短路徑如下所示：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、發，到編號為%d的結點的最短路徑為:n",m);shortest_path(g.vexm,g.vex0,g.vexnum);return 0; ABECD718122通過鏈路狀態算法計算A點到其它各點的cost，最終輸出A的路由表。A的轉發表： 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,它表示當前所找到的從始點到每個終點的最短路徑的長度，它的初態為若有弧則為弧的權值，若無則為無窮大，且U為已經找到最短路徑的結點的集合，首先比

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