實驗三動態(tài)規(guī)劃求多段圖問題

1、實驗項目算法實驗動態(tài)規(guī)劃實驗一、實驗目的1 .掌握動態(tài)規(guī)劃算法的基本思想2 .掌握多段圖的動態(tài)規(guī)劃算法3 .選擇鄰接表或鄰接矩陣方式來存儲圖4、分析算法求解的復雜度。二、實驗內容4 .掌握動態(tài)規(guī)劃算法的基本思想5 .掌握多段圖的動態(tài)規(guī)劃算法6 .選擇鄰接表或鄰接矩陣方式來存儲圖4、分析算法求解的復雜度。三、實驗環(huán)境程序設計語言：c+編程工具：microsoft visual studio 2010四、算法描述和程序代碼#include "stdio.h"# define n 7 / 圖的頂點數(shù)# define k 4 / 圖的段數(shù)# define max 23767int

2、costnn; 成本值數(shù)組int pathk; 存儲最短路徑的數(shù)組void creatgraph() /創(chuàng)建圖的(成本)鄰接矩陣 int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)scanf("%d”,&costij);獲取成本矩陣數(shù)據(jù)void printgraph()/ 輸出圖的成本矩陣 int i,j；printf(" 成本矩陣：n");for(i=0;i<n;i+) for(j=0;j<n;j+)printf("%d ",costij);printf("n");

3、/使用向前遞推算法求多段圖的最短路徑精品資料void frontpath() int i,j,length,temp,vn,dn;for(i=0;i<n;i+) vi=0;for(i=n-2;i>=0;i-) for(length=max,j=i+1;j<=n-1;j+) if(costij>0 && (costij)+vj<length) length=costij+vj; temp=j; vi=length;di=temp;path0=0;起點pathk-1=n-1; 最后的目標for(i=1;i<=k-2;i+) (pathi尸dpat

4、hi-1;/將最短路徑存入數(shù)組中void printpath() int i；for(i=0;i<k;i+) printf("%d ",pathi);int main()creatgraph();printgraph();frontpath();printf("輸出使用向前遞推算法所得的最短路徑：n");printpath();printf("n輸出使用向后遞推算法所得的最短路徑：n");printpath(); printf("n"); return 0;五、實驗結果截圖tk、實驗總結在做實驗的過程中，要按部就班，首先明確實驗目的，然后進行分析，寫算法程序，最后 調試運行，不能粗枝大葉，做的過程要細心謹慎，自己