實驗五分枝限界法最短路徑問題

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法設(shè)計與分析實 驗 報 告實驗項目實驗五實驗類別驗證性學(xué)生姓名王龍學(xué)生學(xué)號201400797完成日期2016-5-6指導(dǎo)教師劉振章實驗成績評閱日期評閱教師劉振章實驗五：分枝限界法【實驗?zāi)康摹繎?yīng)用分枝限界法的算法設(shè)計思想求解單源最短路徑問題?！緦嶒炐再|(zhì)】驗證性實驗?！緦嶒瀮?nèi)容與要求】采用分支限界法編程求源點0到終點6的最短路徑及其路徑長度。要求完成：算法描述寫出程序代碼完成調(diào)試進(jìn)行過程與結(jié)果分析。【算法思想及處理過程】由于要找的是從源到各頂點的最短路徑，所以選用一個數(shù)組存起來.Fenzhi函數(shù): 由于先前賦值時,

2、 用一個二維數(shù)組將結(jié)點的有向圖標(biāo)記存起來了( 有邊為1, 無邊為0 ),并且又用另外一個二維數(shù)組將其權(quán)重存起來了; 首先, 通過雙重for循環(huán), 通過if語句判斷, 如果標(biāo)記為1, 并且相加的權(quán)重小于先前最優(yōu)權(quán)重( 在初始化的時候, 對最優(yōu)權(quán)重賦上一個最大值 ), 則求得最優(yōu)權(quán)重, 并且用一維數(shù)組將權(quán)重存起來, 而且用一維數(shù)組將前驅(qū)結(jié)點存起來.你然后, 一直循環(huán)下去, 直到循環(huán)到目的結(jié)點.【程序代碼】# include <stdio.h># define MAX 9void input (int d, int s, int tMAX, int tiMAX, int n, int k

3、);void fenzhi (int d, int s,int tMAX, int tiMAX, int n, int k);void output (int d, int s, int n);int main ()int n, k;int dMAX, sMAX, tMAXMAX = 0, tiMAXMAX = 0;n = 7; k = 11;printf ("請輸入結(jié)點的個數(shù):");scanf ("%d", &n);printf ("請輸入結(jié)點的邊數(shù):");scanf ("%d", &k);inp

4、ut (d, s, t, ti, n, k);fenzhi (d, s, t, ti, n, k);output (d, s, n);return 0;void input (int d, int s, int tMAX, int tiMAX, int n, int k)int i, j, m, z;printf ("請輸入圖的邊: < i, j, tij > n"); for (z=0; z<k; z+) scanf ("%d %d %d", &i, &j, &m); tij = m; tiij = 1; fo

5、r (i = 0; i < n; i+) /初始化數(shù)組 di = 99; / 賦個最大值 si = -1; void fenzhi (int d, int s,int tMAX, int tiMAX, int n, int k)int i, j, zi;d0=0; s0=-1; for (i=0; i<n; i+)printf ("當(dāng)前擴(kuò)展節(jié)點：%d，權(quán)重：%d : n", i, di);for (j=0; j<n; j+)if (tiij = 1 )if ( dj>tij+di)dj=tij+di; /最短長度sj=i;/前驅(qū)結(jié)點if (j !=

6、n /* && j != 6 */ ) printf ("入隊結(jié)點：%d ,最優(yōu)權(quán)重：%d n", j, dj); printf ("n");void output (int d, int s, int n)int i, j=0, ziMAX;printf ("從源點到各個結(jié)點的最短路徑: n");for (i=0; i<n; i+)printf ("dist%d = %d n", i, di);printf ("n");printf ("從源點到終點的最短路徑長度為: %d n", dn-1);printf ("其路徑為: %d ", n-1);zij = sn-1;printf ("-> %d ", zij);while (zij != 0)j+;zij = szij-1;printf ("-> %d ", zij);printf ("n");【