数据结构-源程序.docVIP

#includeiostream #includestack #includefstream using namespace std; const int MaxNum=100000; class Graph {private: int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中 int Num;//当前顶点数 public: Graph();//构造函数 ~Graph();//析沟函数 void Dijkstra(int start);//单元最短路径算法 }; Graph::Graph()//构造函数 { ifstream input(input.txt,ios::in); if(input==NULL)coutopen error!\n; if(input!=NULL) { inputNum; Adj=new int[Num*Num]; if(Adj==NULL)exit(0); for(int i=0;iNum;i++) for(int j=0;jNum;j++) { inputAdj[i*Num+j]; if(Adj[i*Num+j]==-1) Adj[i*Num+j]=MaxNum; } } } Graph::~Graph()//析构函数 { delete[]Adj; } void Graph::Dijkstra(int start)//单元最短路径算法 { int*dist=new int[Num];//记录最短权值 int*prev=new int[Num];//记录路径 int*s=new int[Num];//s为已经确定好的顶点域 int i,j,k,m;//j记录dist的下标 m=start; for(i=0;iNum;i++)//初始化 { dist[i]=Adj[m*Num+i]; prev[i]=m;//记录源点到顶点的最短路径上，本顶点的前一顶点 s[i]=0;//顶点i不在s域中 } prev[m]=-1;//m是源点前一顶点不存在 s[m]=1;//源点在s域中 for(i=0;iNum-1;i++)//差Num-1个顶点需处理 { int min;//最小权 for(k=0;kNum;k++) if(!s[k])break;//找到仍在顶点-S域中的第一个顶点 min=dist[k]; j=k; for(k=j+1;kNum;k++)//找最小权值的边 if(!s[k]dist[k]min) { min=dist[k]; j=k; } s[j]=1;//放进s域中 for(k=0;kNum;k++)//更新最短路径值 if(!s[k]dist[j]+Adj[j*Num+k]dist[k]) { dist[k]=dist[j]+Adj[j*Num+k];//记录最短路径 prev[k]=j;//记录路径即本顶点k的前驱顶点j }} ofstream output(output.txt,ios::out); if(output==NULL)exit(0); for(k=0;kNum;k++)//输出打印 if(k!=m) { if(dist[k]=MaxNum) { output源点start到顶点k不存在相通的路径endlendl;} else {output源点start到顶点k的最小花费为:dist[k]endl;//输出最小权值 j=k; stackintQ; output路径为:; while(j!=m){Q.push(j);j=prev[j];}//路径存入栈中 Q.push(j); while(Q.size()!=1){outputQ.top()--;Q.pop();}//输出路径 outputQ.top()endlendl;Q.pop();//最后一个元素出栈 }}} int main() {Graph G; cout请输入起点：endl; int start; cinstart; G.Dijkstra(start); getchar(); getchar(); return 0;} #include stdio.h #define N 7 /* 顶点数目 */ #define I 999 /* 表示无穷大 */ int graph[N][N] = { /* 图的邻接矩阵 */ {I, 4, 5, 8, I, I, I},