校园最短路径校园最短路径校园最短路径

#include<iostream> #include <string> //引入标准库中的头文件 #include "graph.h" //引入头文件 using namespace std; /* 前置条件：图不存在 输入：无 功能：图的初始化 输出：无 后置条件：构造一个有值的图 */ template <class T> Graph<T>::Graph(int* a,T* v, int n ) //构造图 { int i,j; vertexNum=n; //顶点数 for (i=0; i<MaxSize; i++) //初始化邻接矩阵 for (j=0; j<MaxSize; j++) //定义边 arc[i][j] = 10000; for ( i=0; i<vertexNum; i++) vertex[i]=v[i]; //存储顶点信息 for (i=0; i<vertexNum; i++) //给边赋置 for (j=0; j<vertexNum; j++) arc[i][j]=*(a+i*n+j); int tt=0; } /* 前置条件：图已存在 输入：无 功能：输出图中所有顶点的数据信息 输出：图中所有顶点的数据信息 后置条件：图保持不变 */ template <class T> void Graph<T>::PutOutVexInfo() //取顶点 { int i=0; //假设源点是第0个顶点，即顶点序号是0 if (i>vertexNum) throw "位置"; //错误抛出异常 else{for(i=0;i<vertexNum;i++){ //输出图中所有的顶点 cout<<vertex[i]<<"\n"; } } } /* 前置条件：图已存在 输入：顶点v1,v2 功能：修改顶点v1、v2的路径 输出：修改后图中所有的路径 后置条件：图保持不变 */ template <class T> void Graph<T>::SetArc(int v1,int v2,int arclength) //修改路径 { //假设源点是第0个顶点，即顶点序号是0 if ( v1>vertexNum|| v2>vertexNum) throw "位置"; //错误抛出异常 else { arc[v1][v2]=arclength; //修改v1顶点到v2顶点的距离 arc[v2][v1]=arclength; } } /* 前置条件：图已存在 输入：无 功能：输出图中所有的路径 输出：图中所有顶点的数据信息 后置条件：图保持不变 */ template <class T> void Graph<T>::PutOutArcInfo() //输出图中所有的路径 { int i=0; //假设源点是第0个顶点，即顶点序号是0 int j=0; if ( i>vertexNum|| j>vertexNum) throw "位置"; //错误抛出异常 else { for(i=0;i<vertexNum;i++){ //输出任意两点之间的路径 for(j=0;j<i;j++){ if(arc[i][j]<10000) //两点之间存在路径 cout<<"从"<<vertex[i]<<"到"<<vertex[j]<<"的路径长度为："<<arc[i][j]<<"\n"; //若两点间有路，则输出该两点间的路径 } } } } /* 前置条件：图已存在 输入：顶点name,位置i 功能：在图中i位置插入一个顶点name 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，图中增加了一个顶点 */ template <class T> void Graph<T>::InsertVex(int num,T name) //在图中插入一个顶点，其编号为i，值为value { //假设源点是第0个顶点，即顶点序号是0 if ( num<0|| num>vertexNum) throw "位置"; //如果num输入不正确抛出异常 int row; //行 int col; //列 int numv; //最后一个顶点所在的位置 numv = vertexNum-1; if(num>-1) //num存在 vertexNum++; //顶点数加1 for(int i=numv;i>num-1;i--) //i从最后一个顶点的下一个位置开始循环 vertex[i]=vertex[i-1]; //把从num位置的顶点到最后一个顶点均向后移一位 vertex[num]=name; //把要插入的顶点的值放在num位置上 for(row=numv;row>=0;row--) //把从num列到最后一列的元素均向下移一列 { for(col=numv;col>=num;col--) arc[row][col+1]=arc[row][col]; arc[row][num]=10000; } for(row=numv;row>=num;row--) //把从num行到最后一行的元素均向下移一行 for(col=0;col<=numv+1;col++) arc[row+1][col]=arc[row][col]; for(col=0;col<vertexNum;col++) arc[num][col]=10000; //把num位置所在的行、列的值均置为无穷大 } /* 前置条件：图已存在 输入：顶点pos 功能：在图中删除顶点pos 输出：如果删除不成功，抛出异常 后置条件：如果删除成功，图中减少了一个顶点,相应顶点所建立的边也消去 */ template <class T> void Graph<T>::DeleteVex(int pos) //删除第pos个顶点 { //假设源点是第0个顶点，即顶点序号是0 if ( pos<0|| pos>MaxSize) throw "位置"; //如果pos输入不正确抛出异常 int row; //行 int col; //列 int numv=vertexNum; //numv等于顶点数 if(pos>-1) //pos存在 { for(int i=pos;i<numv-1;i++) vertex[i]=vertex[i+1]; //把从pos到最后的每个点的位置依次向前移一位 vertexNum--; //顶点数减1 for(row=0;row<numv;row++) { for(col=pos;col<numv;col++) arc[row][col]=arc[row][col+1]; //把从pos列到最后一列的元素均向前移一列 arc[row][numv-1]=10000; //把pos所在的列上的值置为无穷大 } for(row=pos;row<numv;row++) for(col=0;col<numv;col++) arc[row][col]=arc[row+1][col]; //把从pos行到最后一行的元素均向上移一行 } } /* 前置条件：图已存在 输入：顶点v ，endv 功能：假如endv存在，求v到endv的最短路径；假如不输入endv，则求v到任意顶点的最短路径 输出：所求得的最短路径及所经历的位置 后置条件：图保持不变 */ template <class T> void Graph<T>::Dijkstra(int v,int endv) //求最短路径，从v顶点到endv点的最短路径 { if ( v>vertexNum) throw "位置"; //v顶点或endv顶点输出不正确则抛出异常 int numv=vertexNum; //顶点数 int dist[MaxSize]; //最短长度 int path[MaxSize]; //当前找到的最短路径 int s[MaxSize]; //存放源点和已生成的终点的集合 int max= 10000; //代表无穷大 int i,j,k,wm; for(i=0;i<numv;i++) //按网的邻接矩阵确定各顶点最短路径的初值 { dist[i]=arc[v][i]; if(i!=v&& dist[i]< max) //如果v、i之间有路 path[i]=v; //当前找到的最短路径为v else path[i]=-1; //否则v与i顶点不存在路径 s[i] = 0; //给s集合确定初值0 } s[v]=1;dist[v]=0; //将顶点v本身排除在外 for(k =0;k<numv-1;k++) //求其他numv-1各顶点的最短路径 { wm = max;j=v; //确定当前最短路径wm及顶点的序号j for( i=0;i<numv;i++) { if(!s[i]&&dist[i]<wm) //如果v、i之间有路 { j=i; wm = dist[i]; //把当前找到的路径确定为最大值 } } s[j]=1; for(i =0;i<numv;i++) //更新未确定最短路径各顶点的当前最短路径 { if(!s[i]&&dist[j]+arc[j][i]<dist[i]) //如果v、i两点的距离加上i、j小于从v点到j点的距离 { dist[i]=dist[j]+arc[j][i];path[i]=j; //dist[i]取最小值