图论最短路径和最小生成树C++实现代码.docx

按书12页图1-13图得到的最短路#include iostreamusing std::endl;using std::cout;using std::cin;void shortest(int path[],int pathValue[][8],int n,int start,int distance[]);void display(int path[],int distance[],int n,int start);int main(){int pathValue[8][8]={{20,2,8,1,20,20,20,20},{2,20,6,20,1,20,20,20},{8,6,20,7,4,2,2,20},{1,20,7,20,20,20,9,20},{20,1,4,20,20,3,20,9},{20,20,2,20,3,20,4,6},{20,20,2,9,20,4,20,2},{20,20,20,20,9,6,2,20}};//表示点间的距离；int n=8;//点的个数；int path[8];//记录到这一点的前一个点的标号，用于显示后面的路径int start;//要输入的开始位置的点；int distance[8];//存储每个点到达start点的距离值； cout输入起始点endl;cinstart;shortest(path,pathValue,n,start,distance);display(path,distance,n,start);}#include iostream#define MAX 20using std::cout;using std::endl;void shortest(int path[],int pathValue[][8],int n,int start,int distance[]){ //判断出发点有没有邻接点for (int i=0;in;i++){if (pathValue[start][i]!=MAX)break;else if(i==n-1){cout该点为孤立点，无连接endl;return;}//如果无连接则直接返回}//将所有的元素初始化bool isShortest[8];//初始化for(int i=0; in; i++){distance[i] = MAX;//将每个点都赋值为最大path[i] = -1;//路径也是-1；初始化isShortest[i] = false;//所有的点都不在最短集合上} //初始化出发点相邻接的顶点距离for(int i =0; in; ++i){if(pathValue[start][i] != MAX)//s行表示源点为s，列则是s点与其余个点的距离的权值。{//当不为max时，说明第i个点与s点相连接，并且距离就为p[s][i]；distance[i] = pathValue[start][i];path[i] = start;//记录与点i相连的前一个点是s，由于最后计算出的路径每个点都会有前一个点的连接，而且只有一个。故可以用数组进行存储。}}isShortest[start] = true;//说明源点是自己的最短点集中的一员，故为truedistance[start] = 0;//最短点与自己的距离是；int min, temp;//选择最短路径for(int i=1; in; i++)//由于有n个点，而本身不用做比较，从而只有n-1次比较。{ min = MAX;//先将min初始化for(int j=0; jn; j++) //将所有点与源点的距离也就是d[i]来比较，找出最短的那个点，并且最短的经过一次循环之后，在下次循环中排除该点，从剩余的点中寻找if(!isShortest[j] distance[j] min)//表明第j个点如果不是最短点集中的就可以拿来比较了{min = distance[j];//将最短的给mintemp = j;//负责记录最短的点是多少}isShortest[temp] = true;//将t点给标记为最短点的集,更新t相邻点的值再以t点为源点，找出与它临近的点。for(int k=0; kn; ++k){if(pathValue[temp][k] != MAX)//与上面的一致，为max的表明无连接或者是本身。否则什么也不做if(!isShortest[k] distance[k] distance[temp] + pathValue[temp][k])//将最短集点筛除，同时如果点K到s的距离比点t到s 的距离与t到k的距离之和要大，则更新d[k]{distance[k] = distance[temp] + pathValue[temp][k];pa