1、云南財經大學信息學院學生綜合性與設計性實驗報告（ 20132014 學年 第 2 學期 ）周次：第 7 周日期： 2014 年 4 月 17 日地點：班級計專 13-1學學生 1成績生學生 2信息查看“最短路徑.swf”，選擇熟悉的程序設計語言定義有向圖，根據動畫演示求取從實驗名稱有向圖任一結點到其他結點的最短路徑。教該同學是否了解實驗原理：A. 了解B. 基本了解C. 不了解師該同學的實驗能力：A.強 B. 中等C. 差該同學的實驗是否達到要求：A. 達到B. 基本達到C. 未達到評實驗報告是否規范：A. 規范B. 基本規范C. 不規范實驗過程是否詳細記錄：A. 詳細B. 一般C.沒有 語教

2、師簽名：年月日一、實驗內容與目的1.內容查看“最短路徑.swf”，選擇熟悉的程序設計語言定義有向圖，根據動畫演示求取從有向圖任一結點到其他結點的最短路徑。2.實驗目的了解最短路徑的概論，掌握求最短路徑的方法。二、實驗原理或技術路線（可使用流程圖描述）實驗原理： (李燕妮負責設計，周麗瓊負責編程)圖是由結點的有窮集合V 和邊的集合E 組成，求最短路徑用迪杰斯特拉算法：1)適用條件 & 范圍：編輯版 worda) 單源最短路徑 (從源點 s到其它所有頂點 v);b) 有向圖 & 無向圖 (無向圖可以看作 (u,v),(v,u)同屬于邊集 E 的有向圖 )c) 所有邊權非負 (任取

3、(i,j) E 都有 Wij 0);2)算法描述：a)初始化： disv=maxint(v V,v s); diss=0; pres=s; S=s;b)For i:=1 to n1.取 V-S 中的一頂點u 使得 disu=mindisv|v V-S2.S=S+u3.For V-S 中每個頂點v do Relax(u,v,Wu,v)c)算法結束： disi為 s 到 i 的最短距離；prei為 i 的前驅節點三、實驗環境條件（ 使用的軟件環境 ）Microsoft Visual C+6.0四、實驗方法、步驟（列出程序代碼或操作過程）/* 本程序的功能是求圖中任意兩點間的最短路徑*/#inclu

4、de<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>#define ING 9999typedef struct ArcCellint adj;/* 頂點關系類型，用1 表示相鄰， 0 表示不相鄰 */ArcCell,*AdjMatrix;編輯版 word/* 鄰接矩陣 */typedef struct typechar data3;/* 頂點值 */VertexType;typedef structVertexType *vexs; /* 頂點向量 */AdjMatri

5、x arcs; /* 鄰接矩陣 */int vexnum,arcnum; /* 圖的頂點數和邊數*/MGraph;/* 初始圖 */void InitGraph(MGraph *G)int i,nu,mu;printf("n輸入頂點的個數和（邊）弧的個數：");scanf("%d %d",&nu,&mu);G->arcs=(ArcCell *)malloc(nu*sizeof(ArcCell *);for(i=0;i<nu;i+)/* 分配鄰接矩陣空間*/G->arcsi=(ArcCell *)malloc(nu*siz

6、eof(ArcCell);G->vexs=(VertexType *)malloc(nu*sizeof(VertexType); /*分配頂點空間*/編輯版 wordG->vexnum=nu;G->arcnum=mu; /*圖的頂點數和邊數*/void InsertGraph(MGraph *G,int i,VertexType e)if(i<0|i>G->vexnum) return;strcpy(G->vexsi.data,e.data);/* 確定 v1 在圖頂點中的位置*/int Locate(MGraph G,VertexType v1)in

7、t i;for(i=0;i<G.vexnum;i+)if(strcmp(v1.data,G.vexsi.data)=0) return i;return -1;/* 采用數組（鄰接矩陣）和鄰接表表示無向圖*/void CreateUND(MGraph *G)int i,j,k,*p,w;VertexType v1,v2;p=(int *)malloc(G->vexnum*sizeof(int);編輯版 wordfor(i=0;i<10;i+) pi=0;for(i=0;i<G->vexnum;+i) /*初始鄰接表 */for(j=0;j<G->vex

8、num;+j)G->arcsij.adj=ING;for(k=0;k<G->arcnum;+k)printf("n輸入第 %d 條（邊）弧相對的兩個頂點值:n",k+1);scanf("%s %s",v1.data,v2.data);/* 輸入相鄰的兩個點值*/printf(" 輸入它們的權值: ");scanf("%d",&w);i=Locate(*G,v1);j=Locate(*G,v2);/* 用 i 和 j 來確定它們的位置*/G->arcsij.adj=w;/* 輸出鄰接矩

9、陣*/void Pint(MGraph G)int i,j;for(i=0;i<G.vexnum;i+)編輯版 wordfor(j=0;j<G.vexnum;j+)if(G.arcsij.adj!=ING)printf("t%d",G.arcsij.adj);elseif(i=j)printf("t0");else printf("t ");printf("n");/* 對頂點 V0 到其余頂點v 的最短路徑pv 及其帶權長度Dv 若 pvw 為 1，則 w 是從 V0 到 W 當前求得最短路徑上的頂點

10、,finalv 為 1，當且僅當v 屬于 S，即已經求得從v0 到 v 的最短路 */void ShortestPath(MGraph G,int v0,int *p,int *D)int v,u,i,w,min;int *final;final=(int *)malloc(G.vexnum*sizeof(int);編輯版 word/* 分配空間 */for(v=0;v<G.vexnum;+v)finalv=0;Dv=G.arcsv0v.adj;/* 初始化 */for(w=0;w<G.vexnum;+w) pvw=0;/* 設空路徑 */if(Dv<ING)pvv0=1;p

11、vv=1;/*v 到 v0 有路徑 */Dv0=0;finalv0=1;/* 初始化， V0 頂點屬于S 集 */for(i=1;i<G.vexnum;i+)/* 其余 G.vexnum-1 個頂點 */min=ING;for(w=0;w<G.vexnum;+w)/* 求出矩陣這一行的最小值*/if(!finalw) /*W頂點屬于V-S 中 */if(Dw<min)編輯版 wordv=w;min=Dw;finalv=1;/* 離 V0 頂點最近的V 加入 S集*/for(w=0;w<G.vexnum;+w) /*更新當前最短路徑及距離*/if(!finalw&

12、&(min+G.arcsvw.adj<Dw) /* 不是最小的，修改 Dw,Pw*/ Dw=min+G.arcsvw.adj; for(u=0;u<G.vexnum;u+) pwu=pvu;pww=1;free(final);void main()MGraph G;VertexType e;編輯版 wordint i,j;int *p;int *D;InitGraph(&G);p=(int *)malloc(G.vexnum*sizeof(int *);for(i=0;i<G.vexnum;i+)pi=(int *)malloc(G.vexnum*sizeof

13、(int);D=(int *)malloc(G.vexnum*sizeof(int);printf(" 頂點值： n");for(i=0;i<G.vexnum;+i)/* 給圖頂點向量付值*/scanf("%s",e.data);InsertGraph(&G,i,e);CreateUND(&G);/* 構造圖結構 */printf(" 鄰接矩陣為： n");Pint(G);for(i=0;i<G.vexnum;i+)/* 輸出鄰接矩陣*/ShortestPath(G,i,p,D);/* 調用最短函數 */for(j=0;j<G.vexnum;j+)編輯版 wordif(i!=j)printf(" %s到 %s 的最短路徑為%d n",G.vexsi.data,G.vexsj.data,Dj);printf("nn");getch();五、實驗過程原始記錄( 測試數據、圖表 )請給出各個操作步驟的截圖和說明，要求有對時間復雜度和空間復雜度的說明。（共同負責）編輯版 word時間復雜度和空間復雜度分析：時間復雜度為n3