最短路徑Dijkstra算法實驗報告

1、姓名：張進 學(xué)號：03091256 班級：030913班實驗六：編程實現(xiàn)dijkstra 算法求最短路問題.1.需求分析：首先讓用戶輸入一個帶權(quán)的有向圖，輸入時可通過一對一對輸入存在弧的兩個弧頭與弧尾頂點以及弧上的權(quán)值從而輸入整個有向圖。用戶輸入一對對弧后，我們可以采用數(shù)組的形式來進行存儲每個頂點之間的權(quán)值，最后由用戶輸入該有向圖的源點（即每個最短路徑的起點），要求源點必須為剛才輸入的各頂點中的某一個，如果用戶輸入錯誤，程序要給出錯誤信息提示并退出程序。然后，我們可以設(shè)計一個graph這樣的類，將對關(guān)系的各種操作放入其中，然后我們在主函數(shù)中調(diào)運這個類就可以實現(xiàn)最短路問題的求解了。2.概要設(shè)計：

2、.構(gòu)造一個新的類graph:class graphprivate: int arcsmaxmax,pathmaxmax,dmax; int arcnum,vexnum,weight,v0; type a,b,vexsmax;public: void creat_graph(); void show_shortestpath(); void shortestpath_dij();.結(jié)構(gòu)化調(diào)用類中方法的主函數(shù)：int main()graph <char> g; g.creat_graph(); g.shortestpath_dij(); g.show_shortestpath();re

3、turn 0;3.代碼實現(xiàn)：#include <iostream>#define max 100#define infinity int_max enum boolfalse,true; using namespace std;template <typename type>class graphprivate: int arcsmaxmax,pathmaxmax,dmax; int arcnum,vexnum,weight,v0; type a,b,vexsmax;public: void creat_graph(); void show_shortestpath()

4、; void shortestpath_dij();template <typename type> void graph<type>:creat_graph() int i,j,x,y; cout<<"請輸入你要處理的有向圖中包含弧的個數(shù)：" cin>>arcnum; vexnum=0; for(i=1;i<=max;i+) for(j=1;j<=max;j+) arcsij=int_max; for(i=1;i<=arcnum;i+) cout<<"請依次輸入第"<&

5、lt;i<<"條弧的弧頭與弧尾的頂點以及該弧上所附帶的權(quán)值："<<endl; cin>>a>>b>>weight; x=0; y=0; for(j=1;j<=vexnum;j+) if(vexsj=a) x=j; continue; else if(vexsj=b) y=j; continue; if(x=0) vexs+vexnum=a; x=vexnum; if(y=0) vexs+vexnum=b; y=vexnum; arcsxy=weight; cout<<"請輸入該有向圖的源

6、點(即各最短路徑的起始頂點)：" cin>>a; for(i=1;i<=vexnum;i+) if(vexsi=a) v0=i; break; template <typename type> void graph<type>: show_shortestpath() int i,j,k; for(i=1;i<=vexnum;i+) if(i=v0) continue; if(di!=int_max) cout<<"從源點"<<vexsv0<<"到"<&l

7、t;vexsi<<"的最短路徑為："<<endl; for(k=1;k<=pathi0;k+) if(k!=1) cout<<"->" for(j=1;j<=vexnum;j+) if(pathij=k) cout<<vexsj; cout<<" "<<"其最短的路徑長度為："<<di<<endl; else cout<<"無法從源點"<<vexsv0<

8、<"到達頂點"<<vexsi<<"."<<endl; cout<<endl;template <typename type>void graph<type>:shortestpath_dij() int v,w,finalmax,min,i,j; for(v=1;v<=vexnum;v+) finalv=false; dv=arcsv0v; pathv0=0; for(w=0;w<=vexnum;w+) pathvw=false; if(dv<int_max)

9、 pathvv0=+pathv0; pathvv=+pathv0; dv0=0; finalv0=true; for(i=1;i<=vexnum;i+) if(i=v0) continue; min=int_max; for(w=1;w<=vexnum;w+) if(!finalw) if(dw<min) v=w; min=dw; finalv=true; for(w=1;w<=vexnum;w+) if(!finalw&&(min+arcsvw<dw)&&min<int_max&&arcsvw<int_

10、max) dw=min+arcsvw; for(j=0;j<=vexnum;j+) pathwj=pathvj; pathww=+pathw0; int main()graph <char> g; g.creat_graph(); g.shortestpath_dij(); g.show_shortestpath();return 0;4.調(diào)試分析：起先在主函數(shù)中調(diào)用類graph時將類型參數(shù)t賦值為int從而導(dǎo)致用戶輸入的關(guān)系集合r中的元素必須為整數(shù)。經(jīng)分析后將t賦值為char，當用戶輸入的r的元素為int時，我們可以將其轉(zhuǎn)化為char在進行后續(xù)操作，從而實現(xiàn)對用戶輸入的關(guān)系r中元素的無限制。在類graph的模板外定義成員函 g.creat_graph()g.shortestpath_dij()g.shortestpath_dij()時，由于成員函數(shù)中有類型參數(shù)存在，則需要在函數(shù)外進行模塊聲明，并且在函數(shù)名前綴上“類名<類型參數(shù)>”。5.運行結(jié)果：下圖為有向圖g的帶權(quán)鄰接矩陣，運用dijkstra算法計算從a到其余各頂點的最短路徑以及其長度。 a b c d e f 分析可知：a 10 30 100 從a到