Dijkstra算法求最短路

Dijkstra算法尋找網(wǎng)絡(luò)中最短路徑1.實驗?zāi)繕?biāo)給定一個nxn的網(wǎng)絡(luò)鄰接矩陣network[n][n]試?yán)肈ijkstra算法求解任意兩點之間的最短路徑矩陣path[n][n]以及最短路徑長度plength[n][n]。本實驗中網(wǎng)絡(luò)矩陣借助隨機數(shù)函數(shù)rand()生成符合條件矩陣，并將其存入network.txt文本文檔，以便于在實驗結(jié)束后進行進一步的驗證，此后即借助Dijkstra算法的TP標(biāo)號法可得最短路徑矩陣path[n][n]并將其存入path.txt文檔，之后可根據(jù)path矩陣求出最短路徑長度矩陣plength[n][n]矩陣并將其存入pathlength.txt文檔。最后給出plength矩陣中路徑最長的路徑長度并存入到length.txt文檔中。代碼實現(xiàn)#include<iostream>#include<fstream>#include<stdlib.h>#include<string>#include<stdio.h>#include<time.h>#include<math.h>#definemaximum62555usingnamespace::std;intInt_Random(intL){return(unsignedint)(rand()<<8Arand())%L;}voidInit_matrix_network(int**network,intn);//初始化網(wǎng)絡(luò)矩陣voidOutput_matrix_path(int**path,intn);//輸出path矩陣到path.txt文件voidOutput_matrix_pathlength(int**path,intn);//輸出網(wǎng)路中i到j(luò)節(jié)點之間的最短路徑長度到pathlength.txt文件voidDijkstra(intn,intv,int**network,int**path);intmain(void)

{inti,j;intSIZE=10;//SIZE值自己指定int**network=newint*[SIZE];for(i=0;i<SIZE;i++)network[i]=newint[SIZE];for(i=0;i<SIZE;i++){for(j=0;j<SIZE;j++){network[i][j]=0;}}Init_matrix_network(network,SIZE);int**path=newint*[SIZE];for(i=0;i<SIZE;i++)path[i]newint[SIZE];for(i=0;i<SIZE;i++){for(j=0;j<SIZE;j++){path[i][j]0;}}for(i=0;i<SIZE;++i){Dijkstra(SIZE,i,network,path);}Output_matrix_path(path,SIZE);Output_matrix_pathlength(path,SIZE);for(i=0;i<SIZE;i++){delete[]network[i];delete[]path[i];}delete[]network;delete[]path;return0;}voidInit_matrix_network(int**network,intn){ofstreamcoutfile("network.txt");srand((unsignedint)time(NULL));inti,j;

intSIZE1=n;intrand1=0;for(i=1;i<SIZE1;i++){rand1=Int_Random(i);network[i][rand1]1;network[rand1][i]1;}for(i=0;i<SIZE1;i++){for(j=0;j<SIZE1;j++){coutfile<<network[i][j]<"";}coutfile<endl;}coutfile.close();}voidOutput_matrix_path(int**path,intn){inti,j;ofstreamcoutfile3("path.txt");for(i=0;i<n;++i){for(j=0;j<n;++j){coutfile3<<path[i][j]<"";}coutfile3<endl;}coutfile3.close();}voidOutput_matrix_pathlength(int**path,intn){inti,j,node;intlength,maxlen=0;ofstreamcoutfile("pathlength.txt");intplength[n][n];for(i=0;i<n;++i){for(j=0;j<n;++j){

node=j;length0;while(path[i][node]!=-1){length++;node=path[i][node];}plength[i][j]=length;if(maxlen<length)maxlen=length;}}for(i=0;i<n;++i){for(j=0;j<n;++j){coutfile<<plength[i][j]<"";}coutfile<endl;}coutfile.close();ofstreamcoutfilel("length.txt");〃輸出最長路徑長度到到length.txt文件coutfile1<<maxlen<<endl;coutfile1.close();}voidDijkstra(intn,intv,int**network,int**path){intdist[n];intset[n];for(inti=0;i<n;++i){set[i]=0;if(network[v][i]!=0){dist[i]=network[v][i];path[v][i]=v;}else{dist[i]=maximum;path[v][i]=-1;}}set[v]=1;

dist[v]=0;path[v][v]=-1;intmin,v1;for(intk=0;k<n-1;++k){min=maximum;for(intj=0;j<n;++j) //T標(biāo)號中尋找最小值過程{if(set[j]==0&&dist[j]<min){min=dist[j];v1=j;}}set[v1]=1;//將找到的最小T標(biāo)號變?yōu)镻標(biāo)號for(inti=0;i<n;++i)//以變?yōu)镻標(biāo)號后更新網(wǎng)絡(luò){if(set[i]==0&&network[v1][i]&&dist[v1]+network[v1][i]<dist[i]){dist[i]=dist[v1]+network[v1][i];path[v][i]=v1//設(shè)置i節(jié)點到v節(jié)點路徑中i節(jié)點的前一個節(jié)點}}}}實驗演示通過程序運行可得如下結(jié)果:為便于觀察此處假定圖中有10個節(jié)點,通過程序運行可得如下結(jié)果:1) Network「10]「10]:2)/irmt/1/Dijkstra/h1$catnetwork,txt000(i00000000000100102)/irmt/1/Dijkstra/h1$catnetwork,txt000(i000000000001001000010000000001000000001000010000000010000001000001000000001010-100000000tooo1一450088moo1-00066003333-133333h8888888881a-T333333331t一9366666661k-66j2222221i-722D333331-3333catpath,txt說明:path矩陣第i行表示第i個節(jié)點到其余節(jié)點的路徑，要尋找第i個節(jié)點至第j個節(jié)點的最短路徑只需第i行數(shù)據(jù)即可。例:要尋找第0個和第9個節(jié)點的最短路徑只需要看path[10][10]數(shù)組的第0行即可得最短路徑為：3)4)Maxlength:Pathlength[10][10]:3)4)Maxlength:Pathlength[