1、日期迪杰斯特拉算法姓名：陳應學號：20132201專業：軟件工程語言：c+系統：win8日期：2014.11.28指導老師：趙宏宇一、 實驗內容描述：建立字符文件，在文件內輸入如下數據：m(為頂點數)i1 j1 k1(i1,j1構成一條邊，k1為權重)i2 j2 k2 .利用文件內的數據，使用鄰接矩陣，建立又向連通網，采用迪杰斯特拉算法，得到有向連通網單源最短路經。輸出指定頂點到其余頂點的最短路徑及路徑長度。二、 輸入與輸出設計:1， 用標志數組flagN+1表示兩個集合，當flagi=0時表示頂點在集合V-S內，否則在集合S內2， 為集合S和集合V-S內的每個頂點設置一個距離值，集合S內頂點

2、的距離值就為每個頂點的最短路徑，而集合V-S內的頂點距離值為其頂點通過集合S內的頂點到達源點的最短路徑3， 每次從集合V-S中選取距離值最小的頂點，加入到集合S中，此頂點的最短路徑即為通過S中的頂點到達源點的最短路徑，長度為它的此時的距離值。4， 每加入一個頂點到S中后，都要調整集合V-S中頂點的距離值三、 關鍵數據結構與算法:1， 鄰接表存儲網2， 迪杰斯特拉算法求最短路徑四、 測試與結論結論：測試正常，符合要求源代碼：#include"iostream"#include"fstream"using namespace std;#define N 20

3、#define MAX 32767 /*MAX代表無窮大*/typedef int AdiType;AdiType matrixN+1N+1; /鄰接矩陣typedef structint prenode;/表示前點頂點;int pathlength;shortestPath;shortestPath spN+1;int flagN+1=0;/標志數組/*求源點V到其余頂點的最短路徑及長度*/void dijisktra(int v,int n)int i,j,m,k,min;flagv=1;/源點v進入集合Sfor(i=1;i<=n;i+)spi.pathlength=matrixvi

4、;/置距離值if(spi.pathlength!=0)&&spi.pathlength!=MAX)spi.prenode=v;/置前點序號/初始化路徑長度及路徑數組spfor(i=1;i<=n;i+)min=MAX;for(j=1;j<=n;j+)if(flagj=0)&&(spj.pathlength<min)min=spj.pathlength;m=j;/m點距離值最小/從集合V-S中找到距離值最小的點flagm=1;/m點加入集合Sfor(k=1;k<=n;k+)if(flagk=0&&spm.pathlength+

5、matrixmk<spk.pathlength)spk.pathlength=spm.pathlength+matrixmk;spk.prenode=m;/修改邊集數組，調整距離值/*由前點數組求最短路徑*/void path(int v)if(!spv.prenode)return;path(spv.prenode);cout<<spv.prenode<<"->"int main()fstream file("D:tt.txt");int n,i,j,w,v;file>>n;/讀入頂點數for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i=j ) matrixij=0;else matrixij=MAX;while(file>>i>>j>>w) matrixij=w; cout<<"請輸入源點v:"cin>>v;dijisktra(v,n);cout<<"源點"<<v<<"到各頂點最短路徑及路徑長度為:"<<endl;for(i=1;i<=n;i+)if(i!=v)path(i);c