1、福建農林大學計算機與信息學院（程序設計類課程）實驗報告課程名稱：數據結構姓 名：吳秋月系：計算機專 業：計算機科學與技術(專升本年 級：2008級學 號：081806111指導教師：黃思先職 稱：副教授福建農林大學計算機與信息學院實驗報告系： 計科（專升本） 專業： 計算機科學與技術 年級： 08級 姓名： 吳秋月 學號： 081806111 實驗室號：_田514 計算機號： 18 實驗三 Dijkstra最短路徑(驗證性一、 實驗目的和要求1，掌握圖的有關圖相關操作算法2，熟悉圖的基本存儲方法3，了解掌握圖的基本術語二、 實驗內容和原理實驗內容：已知某交通網中，由站點（源點）出發到達等5個結

2、點（終點）的可能路徑如下有向連通網所示。編程計算和輸出從出發到達其它5個結點的最短路徑和路徑的長度。實驗原理：這是一個典型的單源點最短路徑問題，可以利用Dijkstra算法求解。有向連通的交通網信息，可以采用帶權的鄰接矩陣存儲。運用Dijkstra算法計算出各最短路徑上每個終點的前驅站點以及各最短路徑的長度，再利用棧通過回溯的方法輸出最短路徑。三、 實驗環境硬件環境：多媒體實驗室學生用微機局域網環境軟件環境:Windows xp professionalTurbo C/C+ for windows 四、 算法描述及實驗步驟1，算法描述 16 35 69 28 8 19 1 3 5 10 11

3、7 0116135116911 011613511691242011613513166912420116134431636424201161344316353242011613443163532421確定 2確定 6確定 4確定 3確定 5確定2，算法描述及實驗步驟在Turbo C/C+ for windows中新建的名為Dijkstra.c的C程序文件，在編譯窗口編寫程序代碼，若編譯鏈接都通過，則運行程序，得出正確的結果，正確的程序代碼及相關注釋如下所示：#include "stdio.h"#include "conio.h"#include &quo

4、t;alloc.h"#define N0 10 /宏定義一個常量N0值#define infi 32767 /宏定義一個常量infi值typedef int AdjMatrixN0+1N0+1;typedef struct arcnode int v,w; /v表示頂點，w表示權值struct arcnode next;ArcNode;typedef struct node int degree; /表示度ArcNode *first; /指向ArcNode的第一個指針AdjListN0+1;AdjMatrix adjmatrix; /定義一個整形二維數組adjmatrixAdjLi

5、st adjlist;int n; /表示結點個數 void createAdj( int i,j,w,k; / w表示權值，k表示是否的有向圖還是無向圖ArcNode *p;freopen("c:dijkstra.in","r",stdin; /可用文件進行輸入freopen("c:dijkstra.out", "w", stdout; /可用文件進行輸出scanf("%d",&n; /輸入個數nscanf("%d",&k; /K為0時是無向圖,為1是有向圖

6、.for(i=1;i<=n; i+ /初始化鄰接矩陣for(j=1; j<=n; j+if(i=j adjmatrixij=0; /若i=把0賦給adjmatrixijelse adjmatrixij=infi; /若i!=j，把infimax賦給adjmatrixijdo scanf("%d%d%d", &i,&j, &w; /輸入I,j,w的值if(i<1 | i>n | j<1 | j>n /若i、j不在所給的范圍當中，就結束該循環break;adjmatrixij=w; /把w權值寫入i行j列的鄰接距陣里p

7、=adjlisti.first; /頭指針指向p while(p && p->v!=j p=p->next;if(p continue;p=(ArcNode*malloc(sizeof(ArcNode; /給p分配新空間p->v=j; p->w=w; / j賦給p的頂點，w賦給p的權值p->next=adjlisti.first; / p的下一個結點指向adjlisti的頭指針adjlisti.first=p; /鏈表adjlisti的第一個指針在指向p adjlistj.degree+;if(k=0 adjmatrixji=w;p=(ArcNod

8、e*malloc(sizeof(ArcNode; /給p分配新空間p->v=i; p->w=w; / i賦給p的頂點，w賦給p的權值p->next=adjlistj.first; / p的下一個結點指向adjlisti的頭指針 adjlistj.first=p; /鏈表adjlisti的第一個指針在指向p adjlisti.degree+;while(1;void dijkstra(int x / 用dijkstra算法實現最短路徑 int distN0+1, pathN0+1, markN0+1; /*定義3個數組，dist存儲源點到個結點最短路徑，path存儲源點到當前結

9、點路徑上的倒數第2個點，mark存儲的數為2時表示結點未確定，為1時表示結點已確定。*/int i,j,k,min; for(i=1; i<=n; i+ marki=2; /初始化mark為2，表示結點未確定pathi=x; /初始化path為源點xdisti=adjmatrixxi; / 源點x到各點的距離分別寫入distmarkx=1; /x已經確定for(i=1; i<=n-1; i+ min=infi;k=0;for(j=1; j<=n; j+ /在為確定的結點里找出一個路徑最短的if( markj=2 && distj min=distj;k=j;

10、/k為最短路徑的結點markk=1; /k結點已經確定for(j=1; j<=n; j+ if( markj=2 &&distj>distk+(longadjmatrixkj /如果未確定的結點j在經過剛已確定的結點k的路徑比當前結點值小 distj=distk+adjmatrixkj; /*修改結點j的路徑值，路徑值為上一次已確定的結點k的路徑值加上結點新教師姓名到 j 的路徑值 */ pathj=k; /修改結點j的path值為上次已確定的k結點for(i=1; i<=n; i+ if(i!=x如果i不等于源點x printf("%d<-", i; k=pathi;為源點到i路徑上的倒數第2班風建設while(k!=x / 當k不等于循環輸出見附件k=pathk; /直到kprintf("%d:%dn", k, disti; /見附件main(clrscr(; /清屏createAdj(; printf("nDijkstra:n"dijkstra(1; /源點為1，即從1開始。五、 調試過程調試表明調試通過，運行程序便可以得出正確結果。六、 實驗結果輸入相應的數據，得出結果，截圖如下： 七、