通信網(wǎng)基礎(chǔ)及應(yīng)用課程設(shè)計--c語言環(huán)境下d算法完成最短路徑求解(編輯修改稿)
2025-07-10 17:19 本頁面
【文章內(nèi)容簡介】 用 C 語言程序編譯的求最短路徑的程序。 以下為 用鄰接矩陣表示的圖的 Dijkstra 算法的源程序 。 include define MAXVEX 100 typedef char VexType。 typedef float AdjType。 typedef struct {Vextype vexs[MAXVEX]。/*頂點信息 */ AdjType arcs[MAXVEX][MAXVEX]。/*邊信息 */ int n。/*圖的頂點個數(shù) */ } GraphMatrix。 GraphMatrix graph。 typedef struct{ VexType vertex。/*頂點信息 */ AdjType length。/*最短路徑長度 */ int prevex。/*從 v0 到達 vi(i=1,2,...n1)的最短路徑上 vi的前趨頂點 */ 沈 陽 大 學 課程設(shè)計說明書 }Path。 Path dist[6]。/*n 為圖中頂點個數(shù) */ define MAX 1e+8 void init(GraphMatrix* pgraph,Path dist[]) { int i。dist[0].length=0。 dist[0].prevex=0。 dist[0].vertex=pgraphvexs[0]。 pgrapharcs[0][0]=1。/*表示頂點 v0 在集合 U 中 */ for(i=1。ipgraphn。i++)/*初始化集合 VU 中頂點的距離值 */ {dist[i].length=pgrapharcs[0][i]。 dist[i].vertex=pgraphvexs[i]。 if(dist[i].length!=MAX) dist[i].prevex=0。 else dist[i].pervex=1。 } } void dijlstra(GraphMatrix graph,Path dist[]) {int i,j,minvex。AdjType min。 init(amp。graph,dist)。/*初始化，此時集合 U 中只有頂點 v0*/ for(i=1。i。i++) {min=MAX。minvex=0。 for(j=1。j。j++) if(([j][j]==0amp。amp。(dist[j].lengthmin))/*在 VU 中選出距離值最小頂點 */ {min=dist[j].length。minvex=j。} if(minvex==0) break。 /* 從 v0 沒有路徑可以通往集合 VU 中的頂點 */ [minvex][minvex]=1。 /* 集合 VU 中路徑最小的頂點為 minvex */ for(j=1。 j。 j++) /* 調(diào)整集合 VU 中的頂點的最短路徑 */ 沈 陽 大 學 課程設(shè)計說明書 { if([j][j]==1) continue。 if(dist[j].lengthdist[minvex].length+[minvex][j]) { dist[j].length=dist[minvex].length+[minvex][j]。 dist[j].prevex=minvex。 } } } } void initgraph() { int i,j。 =6。 for(i=0。i。i++) for(j=0。j。j++) [i][j]=(i==
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1