數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——校園導(dǎo)游咨詢系統(tǒng)(編輯修改稿)
2025-02-12 17:09 本頁面
【文章內(nèi)容簡介】 if([v1][col]0amp。amp。[v1][col]MaxWeight) return col。 return 1。}(3)/* */typedef struct{ int row。/*行下標(biāo)*/ int col。/*列下標(biāo)*/ int weight。/*權(quán)值*/}RowColWeight。/*邊信息結(jié)構(gòu)體定義*/void CreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e)/*在圖G中插入n個(gè)結(jié)點(diǎn)信息V和e條邊信息E*/{ int i,k。 Initiate(G,n)。/*結(jié)點(diǎn)順序表初始化*/ for(i=0。in。i++) InsertVertex(G,V[i])。/*結(jié)點(diǎn)插入*/ for(k=0。ke。k++) InsertEdge(G,E[k].row,E[k].col,E[k].weight)。/*邊插入*/}(4)/* */void Dijkstra(AdjMGraph G,int v0,int distance[],int path[])/*帶權(quán)圖G從下標(biāo)v0結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短距離distance*//*和最短路徑下標(biāo)path*/{ int n=。 int *s=(int *)malloc(sizeof(int)*n)。 int minDis,i,j,u。 /*初始化*/ for(i=0。in。i++) { distance[i]=[v0][i]。 s[i]=0。 if(i!=v0amp。amp。distance[i]MaxWeight) path[i]=v0。 else path[i]=1。 } s[v0]=1。/*標(biāo)記結(jié)點(diǎn)v0已從集合T加入到集合S中*/ /*在當(dāng)前還未到最短路徑的結(jié)點(diǎn)集中選取具有最短距離的結(jié)點(diǎn)u*/ for(i=1。in。i++) { minDis=MaxWeight。 for(j=0。jn。j++) if(s[j]==0amp。amp。distance[j]minDis) { u=j。 minDis=distance[j]。 } /*當(dāng)已不再存在最短路徑時(shí)算法結(jié)束；此語句對非連通圖是必須的*/ if(minDis==MaxWeight)return。 s[u]=1。/*標(biāo)記結(jié)點(diǎn)u已從集合T加入到集合S中*/ /*修改從v0到其他結(jié)點(diǎn)的最短距離和最短路徑*/ for(j=0。jn。j++) if(s[j]==0amp。amp。[u][j]MaxWeightamp。amp。distance[u]+[u][j]distance[j]) { /*結(jié)點(diǎn)v0經(jīng)結(jié)點(diǎn)u到其他結(jié)點(diǎn)的最短距離和最短路徑*/ distance[j]=distance[u]+[u][j]。 path[j]=u。 } }}(5)/* */includeincludeincludetypedef char DataType。define MaxSize 100define MaxVertices 10define MaxWeight 10000includeincludeincludevoid SgPrint(AdjMGraph g,int n,int distance[],int path[],int j){ /*輸出源點(diǎn)到其他各結(jié)點(diǎn)的最短距離和最短路徑*/ int i。 /*從源結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑及其距離分別為：*/ printf(從該結(jié)點(diǎn)%c到其他各結(jié)點(diǎn)的最短路徑及其距離分別為：\n,[j])。 printf(\n)。//輸出換行符 for(i=0。in。i++) { /*從源結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的最短路徑為*/ printf(從結(jié)點(diǎn)%c到結(jié)點(diǎn)%c的最短路徑為:,[j],[i])。 printf(()。//輸出左括號 if(path[i]!=1)//源點(diǎn)到其他結(jié)點(diǎn)的最短路徑的前一結(jié)點(diǎn)判斷 { if(path[path[i]]!=1)//該前一結(jié)點(diǎn)的前一結(jié)點(diǎn)進(jìn)行判斷 { if(path[path[path[i]]]!=1)//該前一結(jié)點(diǎn)的前一結(jié)點(diǎn)的前一結(jié)點(diǎn)進(jìn)行判斷 { printf(%c,[path[path[path[i]]]])。//輸出相應(yīng)存在的前一結(jié)點(diǎn) } printf(%c,[path[path[i]]])。//輸出應(yīng)存在的前一結(jié)點(diǎn) } printf(%c,[path[i]])。//輸出應(yīng)存在的前一結(jié)點(diǎn)
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1