數(shù)據(jù)結(jié)構(gòu)-源程序

《數(shù)據(jù)結(jié)構(gòu)-源程序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、#include#include#includeusingnamespacestd;constintMaxum=100000;classGraph{private:int*Adj;//保存鄰接矩陣的一維數(shù)組j和k之間權(quán)值存儲(chǔ)在Adj[j*Num+k]中intNum;//當(dāng)前頂點(diǎn)數(shù)public:Graph();//構(gòu)選函數(shù)"Graph();//析溝函數(shù)voidDijkstra(intstart);//單元最短路徑算法}；Graph::Graph()//構(gòu)造閑數(shù){ifstreaminput("input,txt"，

2、ios::in);if(input==NULL)cout〈<〃openerror!〃；if(input!=NULL){input?Num;Adj=ncwint[Num*Num];if(Adj==NULL)exit(0);for(inti=0;i

3、路徑算法{int*dist=newint[Num];//記彔最短權(quán)值int*prev=newint[Num];//記錄路徑int*s=newint[Num];//s為己經(jīng)確定好的頂點(diǎn)域inti,j,k，m;//j記錄dist的下標(biāo)m=start;for(i=0;i〈Num;i++)//初始化dist[i]=Adj[m*Nura+i];prev[i]=m;//記錄源點(diǎn)到頂點(diǎn)的最短路徑上，本頂點(diǎn)的前一頂點(diǎn)s[i]=O;//頂點(diǎn)i不在s域中}prev[ni]=-1;//ni是源點(diǎn)前一頂點(diǎn)不存在s[m]=l;//源點(diǎn)在s域中for(i=0;i＜Num-l;i++)//差N

4、um-1個(gè)頂點(diǎn)需處理{intmin;//最小權(quán)for(k=0;k＜Num;k++)if(!s[k])break;//找到仍在頂點(diǎn)-S域中的第一個(gè)頂點(diǎn)min=dist[k];j=k；for(k=j+l;k＜Nura;k++)//找最小權(quán)值的邊if(!s[k]&&dist[k]〈min){min=dist[k];j=k；}s[j]=l;//放進(jìn)s域屮for(k=0;k＜Num;k++)//更新最短路徑值if(!s[k]&&dist[j]+Adj[j*Num+k]＜dist[k]){dist[k]=dist[j]+Adj[j*Num+k];//記錄最短路徑prev[k]

5、=j;//記錄路徑即本頂點(diǎn)k的前驅(qū)頂點(diǎn)j}}ofstreamoutput("output,txt",ios::out);if(output==NULL)exit(0);for(k=0;k＜Num;k++)//輸出打印if(k!=m){if(dist[k]＞=MaxNum){output＜〈〃源點(diǎn)〃〈＜start〈〈〃到頂點(diǎn)〃＜〈k〈〈〃不存在相通的路徑〃〈＜endl〈＜endl;}else{output〈〈〃源點(diǎn)〃＜〈start＜〈〃到頂點(diǎn)〃＜＜k〈〈〃的最小花費(fèi)為："〈＜dist[k]〈＜endl;//輸出最小權(quán)值j=k；stack〈int〉Q;output＜〈

6、〃路徑為：〃；while(j!=m){Q.push(j);j=prev[j];}//路徑存入棧中Q.push(j);while(Q.size()!=1){output?Q.top()〈＜"~〉’’;Q.pop();}//輸出路徑output?Q.top()?endl?endl;Q.pop();//最后一個(gè)元素出棧}}}intmain(){GraphG;cout〈〈〃請(qǐng)輸入起點(diǎn)：〃〈

7、ineN7^defineI999graph[N][N]二{{I,4,5,8,T,T,T},{I,I,I，6,6,I,I},{I,I,I,5,I,7,I},{I,I,I,I,8,9,9},{I,I,I，I,I,T,5},{I,I,I，I,I,I,4},{I,I,I,1,I,1,1}/*頂點(diǎn)數(shù)目*//*表示無(wú)窮大*//*圖的鄰接矩陣*//*存放拓?fù)湫蛄?//*拓?fù)渑判蚨陻?shù)*/A主函數(shù)*//*最長(zhǎng)最短距離*//*記錄路徑數(shù)據(jù)*/intList[N];intTopologicalOrder0;voidmain(){inti,j,k,1;intee[N],el[N];int

8、path_