實驗五：分枝限界法

HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY算法設(shè)計與分析

實驗報告實驗項目實驗五實驗類別驗證性學(xué)生姓名王龍學(xué)生學(xué)號201400797完成日期2016-5-6指導(dǎo)教師劉振章實驗成績評閱日期評閱教師劉振章實驗五：分枝限界法【實驗?zāi)康摹繎?yīng)用分枝限界法的算法設(shè)計思想求解單源最短路徑問題?！緦嶒炐再|(zhì)】驗證性實驗?！緦嶒瀮?nèi)容與要求】采用分支限界法編程求源點0到終點6的最短路徑及其路徑長度。要求完成：⑴算法描述⑵寫出程序代碼⑶完成調(diào)試⑷進行過程與結(jié)果分析?！舅惴ㄋ枷爰疤幚磉^程】由于要找的是從源到各頂點的最短路徑，所以選用一個數(shù)組存起來Fenzhi函數(shù)：由于先前賦值時，用一個二維數(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>defineMAX9voidinput(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk);voidfenzhi(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk);voidoutput(intd[],ints[],intn);intmain(){intn,k;intd[MAX],s[MAX],t[MAX][MAX]={0},ti[MAX][MAX]={0};n=7;k=11;printf("請輸入結(jié)點的個數(shù):”)；scanf("%d",&n);printf("請輸入結(jié)點的邊數(shù):”)；scanf("%d",&k);input(d,s,t,ti,n,k);fenzhi(d,s,t,ti,n,k);output(d,s,n);return0;}voidinput(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk){inti,j,m,z;printf("請輸入圖的邊:<i,j,t[i][j]>\n");for(z=0;z<k;z++){scanf("%d%d%d”,&i,&j,&m);t[i][j]=m;ti[i][j]=1;}for(i=0;i<n;i++)//初始化數(shù)組{d[i]=99;//賦個最大值s[i]=-1;}}voidfenzhi(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk){inti,j,zi;d[0]=0;s[0]=-1;for(i=0;i<n;i++){printf("當(dāng)前擴展節(jié)點：%d,權(quán)重：%d:\n",i,d[i]);for(j=0;j<n;j++){if(ti[i][j]==1){if(d[j]>t[i][j]+d[i]){d[j]=t[i][j]+d[i];//最短長度s[j]=i;〃前驅(qū)結(jié)點}if(j!=n/*&&j!=6*/)printf("入隊結(jié)點：%d，最優(yōu)權(quán)重：%d\n",j,d[j]);}}printf("\n");}}voidoutput(intd[],ints[],intn){inti,j=0,zi[MAX];printf("從源點到各個結(jié)點的最短路徑:\n");for(i=0;i<n;i++)printf("dist[%d]=%d\n”,i,d[i]);printf("\n");printf("從源點到終點的最短路徑長度為:％d\n",d[n-1]);printf("其路徑為:%d",n-1);zi[j]=s[n-1];printf("---->%d”,zi[j]);while(zi[j]!=0){j++;zi[j]=s[zi[j-1]];printf("---->%d”,zi[j]);【運行結(jié)果】11：."F:'\ci^'WR5^\Deb□g\dfdsa.sue-'—□X請輸入結(jié)點的個數(shù);7請輸入結(jié)點的邊數(shù)：11請