實(shí)驗(yàn)五分枝限界法最短路徑問題

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

2、 用一個(gè)二維數(shù)組將結(jié)點(diǎn)的有向圖標(biāo)記存起來了( 有邊為1, 無邊為0 ),并且又用另外一個(gè)二維數(shù)組將其權(quán)重存起來了; 首先, 通過雙重for循環(huán), 通過if語句判斷, 如果標(biāo)記為1, 并且相加的權(quán)重小于先前最優(yōu)權(quán)重( 在初始化的時(shí)候, 對最優(yōu)權(quán)重賦上一個(gè)最大值 ), 則求得最優(yōu)權(quán)重, 并且用一維數(shù)組將權(quán)重存起來, 而且用一維數(shù)組將前驅(qū)結(jié)點(diǎn)存起來.你然后, 一直循環(huán)下去, 直到循環(huán)到目的結(jié)點(diǎn).【程序代碼】# 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é)點(diǎn)的個(gè)數(shù):");scanf ("%d", &n);printf ("請輸入結(jié)點(diǎn)的邊數(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; / 賦個(gè)最大值 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é)點(diǎn)：%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é)點(diǎn)if (j !=

6、n /* && j != 6 */ ) printf ("入隊(duì)結(jié)點(diǎn)：%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 ("從源點(diǎn)到各個(gè)結(jié)點(diǎn)的最短路徑: n");for (i=0; i<n; i+)printf ("dist%d = %d n", i, di);printf ("n");printf ("從源點(diǎn)到終點(diǎn)的最短路徑長度為: %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");【