1、數 據 結 構 學院： 姓名： 班級： 學號：實習三 圖及其應用題目：試設計一個算法，求圖中一個源點到其他各頂點的最短路徑。一.需求分析：設計要求：（1）用鄰接表表示圖； （2）按長度非遞減次序打印輸出最短路徑的長度及相應路徑。二.設計思想：本程序使用鏈表的形式存儲的。根據書上的德克斯德拉算法的思想，初始狀態時，集合s中只包含源點，設為v0，然后不斷地從集合T中選擇到源點v0路徑長度最短的結點u加入到集合s中，集合s中每加入一個新的結點u都要修改從源點v0到集合T中剩余結點的當前最短路徑長度值，集合T中各結點的新的當前最短路徑的長度值，為原來的最短路徑的長度值與從源點過結點u到達該結點的路徑長

2、度中的最小者。此過程不斷地重復，直到集合T中的結點全部加入到集合s中為止。三設計提示題中規定采用鄰接表表示圖，假設圖中有n個頂點，則考慮鄰接表表 頭結點為head0，head1，head2，headn-1，鏈表中每個結點有 三個字段： 其中，vertex頂點字段，存放頂點序號； cost表頭頂點到該頂點之邊上的權值； link連接同一鏈中的下一個頂點。 采用數組distj(0jn-1)存放從源點v0到頂點vj的最短路徑長度， dist0=0，如果源點v0到頂點vx無通路，則distx=max（計算機允許的最 大值）。 采用n-1個數組分別存放源點v0到其余n-1個頂點之最短路徑上的頂點 （序號

3、）。采用數組S指示已找到最短路徑的頂點。Sj=0表示頂點j不在 數組中，Sj=1表示頂點j在數組中(0jn-1)。四.設計思想打印構圖求最短路徑調用creatgraph輸入點邊信息輸出（可用遞歸）排序構圖比較簡單。求最短路徑是修改的書上的Dijkstra函數，書上的圖是用鄰接矩陣存儲的，我按照題目要求改為鄰接鏈表，但是思想一樣。排序借用了冒泡排序法。輸出最短路徑是自己設計的一個遞歸函數。函數體如下：void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*帶權圖G從下標v0頂點到其它頂點的最短距離distance*/*和最短路徑下標

4、path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)malloc(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i < n; i +) distancei =MaxWeight; si = 0; pathi = -1; distancev0=0; p=G.av0.adj; while(p!=NULL) distancep->dest=p->cost; pathp->dest=G.av0.data; p=p->next; sv0 = 1; /*在還未找到最

5、短路徑的頂點集中選有最短距離的頂點u*/ for(i = 1; i < n; i +) minDis = MaxWeight;for(j = 0;j <=n;j +) if(sj = 0 && distancej < minDis) u = j; minDis = distancej; /*當已不再存在路徑時算法結束*/if(minDis = MaxWeight) return;su = 1; /*標記頂點u已從集合T加入到集合S中*/*修改從v0到其它頂點的最短距離和最短路徑*/p=G.au.adj;while(p!=NULL) if(sp->dest

6、 = 0 && distanceu +p->cost < distancep->dest) distancep->dest = distanceu +p->cost; pathp->dest =G.au.data; p=p->next; void printpath(int i,int start,int path,int a) int j,u; u=0; if(pathi=start) printf("%d",start); return;for(j=0;j<6;j+)if(aj!=pathi)u+;if(a

7、j!=pathi)break; printpath(u,start,path,a); printf("%d",pathi); 源代碼：#include <stdio.h>#include <malloc.h>typedef int DataType;#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000/*鄰接表的存儲結構*typedef struct Node int cost;int dest;/*鄰接邊的弧頭頂點序號*/struct

8、 Node *next;Edge;/*鄰接邊單鏈表的結點結構體*/typedef structDataType data;/*頂點數據元素*/int source;/*鄰接邊的弧尾頂點序號*/Edge *adj;/*鄰接邊的頭指針*/ AdjLHeight; /*數組的數據元素類型結構體*/typedef struct AdjLHeight aMaxVertices;/*鄰接表數組*/ int numOfVerts;/*頂點個數*/ int numOfEdges;/*邊個數*/ AdjLGraph;/*鄰接表結構體*/typedef structint row;int col;int weig

9、ht;RowCol;void AdjInitiate(AdjLGraph *G)int i;G->numOfVerts=0;G->numOfEdges=0;for(i=0;i<MaxVertices;i+)G->ai.source=1;G->ai.adj=NULL;void InsertVertex(AdjLGraph *G,int i,DataType vertex)if(i>=0&&i<MaxVertices)G->ai.data=vertex;G->numOfVerts+;else printf("定點越界&

10、quot;);void InsertEdge(AdjLGraph *G,int v1,int v2,int cost)Edge *p;if (v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts) printf("v1 or v2越界");return ;p=(Edge *)malloc(sizeof(Edge);p->dest=v2;p->cost=cost;p->next=G->av1.adj;G->av1.adj=p;G->numOfEdges+;int Ge

11、FirstVex(AdjLGraph *G,int v)Edge *p;if (v<0|v>=G->numOfVerts) printf("v越界");return -1;p=G->av.adj;if(p!=NULL)return p->dest;else return -1;int GetNextVex(AdjLGraph *G,int v1,const int v2)Edge *p;if (v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts) printf(&quo

12、t;v1 or v2越界");return -1;p=G->av1.adj;while(p!=NULL)if(p->dest!=v2)p=p->next;continue;else break;p=p->next;if(p!=NULL)return p->dest;else return -1;void CreateGraph(AdjLGraph *G,DataType v,int n,RowCol d,int e)int i,k;AdjInitiate(G);for(i=0;i<n;i+) InsertVertex(G, i,vi);for(k=

13、0;k<e;k+)InsertEdge(G,dk.row,dk.col,dk.weight);/*zhunbeigongzuo*/88888888888888888888888888888888888888888888888888888888888888888888888888888void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*帶權圖G從下標v0頂點到其它頂點的最短距離distance*/*和最短路徑下標path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)mallo

14、c(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i < n; i +) distancei =MaxWeight; si = 0; pathi = -1; distancev0=0; p=G.av0.adj; while(p!=NULL) distancep->dest=p->cost; pathp->dest=G.av0.data; p=p->next; sv0 = 1; /*在還未找到最短路徑的頂點集中選有最短距離的頂點u*/ for(i = 1; i < n; i +) minDis =

15、MaxWeight;for(j = 0;j <=n;j +) if(sj = 0 && distancej < minDis) u = j; minDis = distancej; /*當已不再存在路徑時算法結束*/if(minDis = MaxWeight) return;su = 1; /*標記頂點u已從集合T加入到集合S中*/*修改從v0到其它頂點的最短距離和最短路徑*/p=G.au.adj;while(p!=NULL) if(sp->dest = 0 && distanceu +p->cost < distancep->

16、;dest) distancep->dest = distanceu +p->cost; pathp->dest =G.au.data; p=p->next; /8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888/8888888888888888888888888888888888888888888888888888888888888void BubbleSort(DataType a,int distance,int path

17、,int n)int i,j,flag=1;DataType temp;for(i = 1;i < n && flag = 1; i+) flag = 0; for(j = 0;j < n - i; j+) if(distancej>distancej+1) flag = 1; temp = aj; aj = aj+1; aj+1 = temp;temp = pathj; pathj = pathj+1; pathj+1 = temp;temp = distancej; distancej = distancej+1; distancej+1 = temp;

18、void printpath(int i,int start,int path,int a) int j,u; u=0; if(pathi=start) printf("%d",start); return;for(j=0;j<6;j+)if(aj!=pathi)u+;if(aj!=pathi)break; printpath(u,start,path,a); printf("%d",pathi); /88888888888888888888888888888888888888888888888888888888888888888888888main()AdjLGraph g1;int aMaxVertices;RowCol rowMaxEdges;int i,j,k,v0;int distance6,path6;printf("請輸入圖的點的個數");scanf("%d",&i);printf("請輸入圖的邊的個數");scanf("%d",&j);for(k=0;k<i;k+)printf("請輸入圖的點");scanf("%d",&ak);for(k=0;k<