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

《图论最短路径和最小生成树c++实现代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、按书12页图1-13图得到的最短路#includeusingstd::endl;usingstd::cout;usingstd::cin;voidshortest(intpath[],intpathValue[][8],intn,intstart,intdistance[]);voiddisplay(intpath[],intdistance[],intn,intstart);intmain(){intpathValue[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}

2、,{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}};//表示点间的距离；intn=8;//点的个数；intpath[8];//记录到这一点的前一个点的标号，用于显示后面的路径intstart;//要输入的开始位置的点；intdistance[8];//存储每个点到达start点的距离值；cout<<"输入起始点"<>start;shortest(path,pathValue,n,start,

3、distance);display(path,distance,n,start);}#include#defineMAX20usingstd::cout;usingstd::endl;voidshortest(intpath[],intpathValue[][8],intn,intstart,intdistance[]){//判断出发点有没有邻接点for(inti=0;i

4、直接返回}//将所有的元素初始化boolisShortest[8];//初始化for(inti=0;i

5、e[start][i];path[i]=start;//记录与点i相连的前一个点是s，由于最后计算出的路径每个点都会有前一个点的连接，而且只有一个。故可以用数组进行存储。}}isShortest[start]=true;//说明源点是自己的最短点集中的一员，故为truedistance[start]=0;//最短点与自己的距离是；intmin,temp;//选择最短路径for(inti=1;i

6、找出最短的那个点，并且最短的经过一次循环之后，在下次循环中排除该点，从剩余的点中寻找if(!isShortest[j]&&distance[j]

7、!isShortest[k]&&distance[k]>distance[temp]+pathValue[temp][k])//将最短集点筛除，同时如果点K到s的距离比点t到s的距离与t到k的距离之和要大，则更新d[k]{distance[k]=distance[temp]+pathValue[temp][k];path[k]=temp;//同时标记k点与t点相连接；}}}}#includeusingstd::endl;usingstd