dijst.zip_Dijst算法_Dijst算法代码_dijst

#include <iostream> #include<string.h> using namespace std; class DN{ public: DN(); void createDN(DN G); void show(); void shortestpath_dij(DN G,int P[][6],int D[6]); private: int s[6][6]; // int vexnum; //顶点数; int D[6]; int P[6][6]; }; DN::DN(){ for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ s[i][j]=9999; } } } void DN::createDN(DN G){ cout<<"输入<v1,v2>(0-5)以及权值,权值输入9999时结束"<<endl; int v1=0,v2=0,w=0;//G.vexnum=0; while(w!=9999){ cin>>v1; cin>>v2; cin>>w; s[v1][v2]=w; //G.vexnum++; } //G.vexnum--; //cout<<G.vexnum<<endl; } void DN::show(){ for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ cout<<s[i][j]<<' '; } cout<<endl; } } void DN::shortestpath_dij(DN G,int P[][6],int D[6]){ int v,w; bool final[6]; for(v=0;v<6;++v){ final[v]=false;D[v]=s[0][v]; //for(w=0;w<vexnum;++w)P[w][v]=false; //if(D[v]<9999){P[v][0]=true;P[v][v]=true;} } D[0]=0;final[0]=true; for(int i=1;i<6;++i){ int min=9999; for(w=0;w<6;++w) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=true; for(w=0;w<6;++w) if(!final[w]&&(min+s[v][w]<D[w])){ D[w]=min+s[v][w]; for(int t=0;t<6;t++){ P[w][t]=P[v][t]; //cout<<P[w][t]<<endl; } //P[w][w]=true; } } } int main(){ DN a; a.createDN(a); a.show(); int P[6][6]; int D[6]; a.shortestpath_dij(a,P,D); int i,j; for(i=0;i<6;i++){ for(j=0;j<6;j++){ cout<<P[i][j]<<' '; } cout<<endl; } return 0; }