求單源最短路徑—Dijkstra算法實驗報告

1、 本科學生綜合性實驗報告項目組長 楊濱 學號 0123707 成 員 楊濱 專 業(yè)軟件工程 班級 12軟件 2班 實驗項目名稱 求單源最短路徑dijkstra算法 指導教師及職稱趙曉平 講師 開課學期 13 至14 學年一學期上課時間 2013 年 9 月 1 日學生實驗報告三（綜合性實驗）學生姓名楊濱學號0123707同組人實驗項目求單源最短路徑dijkstra算法必修 選修演示性實驗 驗證性實驗 操作性實驗 綜合性實驗實驗地點w101實驗儀器臺號指導教師趙曉平實驗日期及節(jié)次2013.12.17(二) 12節(jié)2013.12.19(一) 89a節(jié)一、實驗綜述1、實驗目的及要求 （1）了解求最優(yōu)

2、化問題的貪心算法，了解貪心法的基本要素，學會如何使用貪心策略設計算法； （2）了解單源最短路徑問題，掌握dijkstra算法的思想； （3）編寫程序，利用dijkstra算法實現(xiàn)，求任意兩點間的單源最短路徑。實驗題： 給出如右有向圖的邊權圖，求任意兩點間的單源最短路徑。 實驗要求：認真完成實驗題，能正確運行，提交實驗報告并上傳程序，實驗報告要求寫出操作步驟、結果、問題、解決方法、體會等。2、實驗儀器、設備或軟件 計算機、vc+6.0、office、相關的操作系統(tǒng)等。二、實驗過程（實驗步驟、記錄、數(shù)據(jù)、分析）#include<iostream>using namespace std;

3、/*void graph(int n,bool *ins,int a66,int *d)ins=new booln;ins0=0;for(int i=1;i<n;i+)insi=1;a=new int*n;for(i=0;i<n;i+)ai=new intn;cout<<"input "<<endl;for(i=0;i<n;i+)for(int j=0;j<n;j+)cin>>aij;d=new intn;for(i=0;i<n;i+)di=a0i;*/int choose(int n,int *d,bool

4、 *s)int i,minpos=-1,min=500;for(i=1;i<n;i+)if(di<min && !si) min=di;minpos=i; return minpos;void dijkstra(int s,int n,bool *ins,int *d,int *path,int a66)int k,i,j;for(i=0;i<n;i+)insi=false;di=asi;if(i!=s && di<500) pathi=s;else pathi=-1;inss=true;ds=0;for(i=0;i<n-1;i+)

5、k=choose(n,d,ins); insk=true; for(j=0;j<n;j+) if(!insj && dk+akj<dj) dj=dk+akj;pathj=k; void display(int s,int n,int a66,int *d,int *path) int t,m;cout<<"a"<<n<<""<<n<<": "<<endl;for(int i=0;i<n;i+)for(int j=0;j<n;

6、j+)cout<<aij<<" "cout<<endl;cout<<"輸入終點: "cin>>t;cout<<"距離為 d"<<t<<": "<<dt<<" "cout<<"路徑為: "<<t;while(t!=s)m=patht;cout<<m;t=m;cout<<endl;int main()int n,*

7、d,*path;/*a,bool *ins;int a66=0,50,10,500,70,500,500,0,15,500,10,500,20,500,0,15,500,500,500,20,500,0,35,500,500,500,500,30,0,500,500,500,500,3,500,0;cout<<"input n: "cin>>n;ins=new booln;/*a=new int*n;for(i=0;i<n;i+)ai=new intn;cout<<"input "<<endl;for

8、(i=0;i<n;i+)for(int j=0;j<n;j+)cin>>aij;*/path=new intn;d=new intn;/graph(n,ins,a,d);int s=0;dijkstra(s,n,ins,d,path,a);display(s,n,a,d,path);return 0;三、結論1、實驗結果2、分析討論這個實驗稍微復雜些，在實現(xiàn)算法時遇到好多問題，首先要實現(xiàn)距離的算法：圖中的數(shù)等同于下圖：   1 2 3 4 5 6 然后經過dijkstra算法分析求出最短路徑， 1  0 50 

9、  10         70        通過這道程序，我明白了：你有了一個算法，2     0    15      10         要通過程序去實現(xiàn)它非常復雜，以后需要勤3  20  &

10、#160;    0   15                 學苦練，加以熟練才能將算法變成程序。4     20      0   35             5           30   0             6