運籌學c語言實現dijkstra算法求解圖的最短路徑

《運籌學c語言實現dijkstra算法求解圖的最短路徑》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、西安科技大學運籌學課程設計報告姓名：袁薪洋一、算法思想運用Dijkstra算法求解圖的最短路徑。Dijkstra算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑,就將加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對

2、應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。二、算法流程或步驟Dijkstr算法具體步驟：（1）初始時，S只包含源點，即S＝，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或）（若u不是v的出邊鄰接點）。（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（uU）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修

3、改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權。（4）重復步驟（2）和（3）直到所有頂點都包含在S中。一、算法源程序#includeintm;intn;floata[100][100];floatdist[100];intprev[100];floatMAX_VALUE=10000;voiddijkstra(){if(m<0

4、

5、m>n)//當無頂點的情況return;bool*s=newbool[n+1];for(inti=0;i

6、e;if(dist[i]==MAX_VALUE)//與源點無連接的頂點prev[i]=0;//設置對應權值為elseprev[i]=m;//與源點相連接的頂點設置為m}dist[m]=0;s[m]=true;for(inti1=0;i1

7、++)if((!s[j1])&&(a[u][j1]

8、;}while(temp!=m);cout<<"(源位置)。最短路徑長度為："<>n;cout<<"請分別對兩頂點之間賦權值(若無此連接，賦'0'值,請注意兩頂點之間的方向):"<>a[i][j];if(a[i][j]==0)a[i][j]=MAX_VALU

9、E;}cout<<"請輸入此帶權有向圖的源頂點的編號：";cin>>m;dijkstra();path();}一、算例和結果例：設0為源點，求0到其他各頂點（1、2、3）的最短路徑。