最短路徑的求解

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計最短路徑的求解學院 計算機科學與技術(shù)專業(yè) 計算機科學與技術(shù)班級 042班姓名 肖虎成學號 20044440214指導老師 余童蘭實驗報告題目：最短路徑的求解一需求分析： 對有向圖進行掃描，確定從v0到各點的最短路徑。 首先選擇儲存結(jié)構(gòu)，然后采用迪杰斯特拉算法，最后打印。 具體如下：輸入頂點和邊數(shù)6，7用一結(jié)構(gòu)體保存圖的基本信息，并初始化。輸入頂點向量012345輸入各邊的起點，終點和權(quán)值0,2,10#0,4,30#0,5,100#1,2,5#2,3,50#3,5,10#4,3,20#4,5,60#對圖中信息的儲存對圖進行掃描，尋找最短路徑打印從定結(jié)點到其余各點的最短路徑二.設(shè)計

2、概要 主函數(shù)分配圖儲存空間G G調(diào)用creat(G); G調(diào)用spath(G,0,p) G，p調(diào)用print(G,p)四個成員arcsMAXMAX，vexnum，arcnumvexsMAX頂點數(shù)vexnum和邊數(shù)arcnum，輸入頂點向量vexsMAX，輸入各條邊的起點，終點和權(quán)值保存在鄰接矩陣arcsMAXMAX中 &G1選擇初始最短路徑，放集合s（finalMAX）2，修改從v0到集合v-s任意頂點的最短路徑，保存在DMAX中，路徑的結(jié)點保存在PMAXMAX3，重復操作n-1次。 &G,&p打印最短路徑 &G,&p1主函數(shù)的設(shè)計方案。首先構(gòu)造有向圖，

3、然后對有向圖進行輸入，接著采用迪杰斯特拉算法求最短路徑，最后打印到各個節(jié)點的最短路徑。 2圖的儲存結(jié)構(gòu)設(shè)計。定義結(jié)構(gòu)體，其中包括4個成員： 3輸入函數(shù)設(shè)計。輸入頂點數(shù)和邊數(shù)，輸入頂點向量，輸入各條邊的起點，終點和權(quán)值分別保存在結(jié)構(gòu)體的頂點數(shù)，邊數(shù)，頂點向量和鄰接矩陣中。 4迪杰斯特拉算法。掃描鄰接矩陣，保存最短路徑，然后增加路徑，更新最短路徑，返回G和路徑數(shù)組p. 5打印函數(shù)。 三詳細設(shè)計 /最短路徑迪杰斯特納算法# define MAX 6 #define N 999# define T 1#define F 0#define null 0# include "stdio.h&qu

4、ot;#include "malloc.h"typedef struct MGraph char vexsMAX; /頂點向量 int arcsMAXMAX; /鄰接矩陣 int vexnum;int arcnum; /圖當前頂點數(shù)和邊數(shù) MGraph;struct MGraph *creat (MGraph *G) /圖的輸入函數(shù) int i,j,k; int v1,v2,w; printf("請輸入頂點數(shù)和邊數(shù):n"); scanf ("%d,%d",&G->vexnum,&G->arcnum); /輸

5、入頂點數(shù)和邊數(shù) getchar(); printf("請輸入頂點向量:n"); for(i=0;i<G->vexnum;+i) scanf("%c",&G->vexsi); /輸入頂點向量 for(i=0;i<G->vexnum;+i) for(j=0;j<G->vexnum;+j) G->arcsij=N; /鄰接矩陣初始化 printf("請輸入各條邊的起點，終點和權(quán)值n"); for(k=0;k<G->vexnum;+k) scanf("%d,%d,%

6、d#",&v1,&v2,&w); G->arcsv1v2=w; /將權(quán)值存入鄰接矩陣 void spath (MGraph *G,int v0,int PMAXMAX) /迪杰斯特納算法 int finalMAX,DMAX; /finalv表示v是屬于s，Dv表示最短路徑 / p存放路徑 int i,j,v,w, min; for(v=0;v<G->vexnum;v+) finalv=F;Dv=G->arcsv0v; /將直接相連的路徑保存為最短路徑for(w=0;w<G->vexnum;w+) Pvw=F; if(Dv&l

7、t;N)Pvv0=T;Pvv=T; /如果v點與v0直接相連，將節(jié)點保存在p中 Dv0=0;finalv0=T; /v0到v0路徑為0 for(i=1;i<G->vexnum;i+) min=N; /初始化min為無窮大 for(w=0;w<G->vexnum;w+) if(!finalw) if(Dw<min)v=w;min=Dw; /w為s中路徑最短的節(jié)點，并賦值為v節(jié)點 finalv=T; / 將v節(jié)點置于s中 for(w=0;w<G->vexnum;w+) if(!finalw&&(min+G->arcsvw<Dw)

8、 Dw=min+G->arcsvw; /如果w節(jié)點到v0更近，更新節(jié)點路徑 for(j=0;j<G->vexnum;j+) Pwj=Pvj; Pww=T; /將路徑節(jié)點保存在p中 void print (MGraph *G,int pMAXMAX) int v,w;printf("n最短路徑為:n"); for(v=1;v<G->vexnum;v+) printf("v%d to v%d :",0,v); for(w=0;w<G->vexnum;w+) if(pvw) /如果節(jié)點v到節(jié)點w有路徑，則打印出來 pr

9、intf(" %c,",G->vexsw); printf("n"); main()MGraph *G; int pMAXMAX; G=(MGraph *)malloc(sizeof(MGraph); /分配空間 creat(G); /輸入構(gòu)造圖 spath(G,0,p); /求最短路徑 print(G,p); /打印最短路徑 getch();四調(diào)試情況請輸入頂點數(shù)和邊數(shù)：6，7請輸入頂點向量：012345請輸入各條邊的起點，終點和權(quán)值0,2,10#0,4,30#0,5,100#1,2,5#2,3,50#3,5,10#4,3,20#4,5,60#最短路徑為：v0 to v1:v0 to v2: 0, 2,v0 to v3: 0, 2, 3,v0 to v4: 0, 4,v0 to v5: 0, 2, 3, 5,五：總結(jié) 本實驗中