4012最长的最短路径的求解

科技前沿 • 2025-01-14 16:33 • 阅读 66

大家好，我是讯享网，很高兴认识大家。

描述

设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点。

输入

多组数据，每组数据m+2行。每组数据第一行为两个整数n和m，代表有n个顶点m条路。顶点编号为1到n。第二行到第m+1行每行有三个整数a，b和c，代表顶点a和顶点b之间有一条长度为c的路。第m+2有一个整数v，代表顶点v。当n和m都等于0时，输入结束。

输出

讯享网

每组数据输出两行。第一行为最短路径最长的顶点编号c，第二行为两点的最短距离d。

输入样例 1

4 4 1 2 1 2 3 1 3 4 1 2 4 1 4 4 3 1 2 3 2 3 2 2 4 6 3 0 0

讯享网

输出样例 1

讯享网1 2 4 8

//最长的最短路径的求解 #include <iostream> #define MVNum 100//最大顶点数 #define MaxInt 32767 //最长长度（无穷大） using namespace std; typedef struct{ int vexs[MVNum];//顶点表 int arcs[MVNum][MVNum];//邻接矩阵 int vexnum,arcnum; }AMGraph; void Create_V(AMGraph &G,int name){ int pos=++G.vexnum; G.vexs[pos-1]=name;//存入点名 for(int i=1;i<=pos;i++){//点所在的行列清零 G.arcs[i-1][pos-1]=0; G.arcs[pos-1][i-1]=0; } } void Create_Arc(AMGraph &G,int h,int k,int len){ G.arcs[h-1][k-1]=G.arcs[k-1][h-1]=len;//点与对称点都归1 G.arcnum++; } void Dijsktra(AMGraph G){//输入图，进行Dijsktra运算(由于不需要输出路径，本次算法没有使用Path int v; //起点 int D[G.vexnum],V[G.vexnum];//D表示起点到这个点的距离，V表示这个点的最短距离是否已经确定 cin>>v; for(int i=1;i<=G.vexnum;i++){//初始化所有 D、V D[i-1]=G.arcs[v-1][i-1]; V[i-1]=0; } for(int i=1;i<=G.vexnum-1;i++){//最多进行vexnum次更新 int min=MaxInt;//一轮中离起点最近的距离 int mv=0;//一轮中距离起点最近的点 for(int j=1;j<=G.vexnum;j++)//获取一轮中G-V中离起点最近的点 if(D[j-1]<min&&!V[j-1]){ min=D[j-1]; mv=j; } V[mv-1]=1; for(int j=1;j<=G.vexnum;j++){//更新以G-V中离起点最近的点位入度的所有边的出度点离起点最近的距离 if(D[mv-1]+G.arcs[mv-1][j-1]<D[j-1]) D[j-1]=D[mv-1]+G.arcs[mv-1][j-1]; } } int max=0;//最长的最短路径 int mv=0;//最长的最短路径编号 for(int i=1;i<=G.vexnum;i++){ if(D[i-1]>max){ max=D[i-1]; mv=i; } } cout<<mv<<endl<<max<<endl; } void Calculate(int m,int n){ AMGraph G; G.vexnum=G.arcnum=0; for(int i=1;i<=m;i++) Create_V(G,i);//构造前n个顶点 for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) G.arcs[i-1][j-1]=MaxInt; for(int i=1;i<=n;i++){//构造n条边 int h,k,len; cin>>h>>k>>len;//输入左右顶点 Create_Arc(G,h,k,len);//构造边 } Dijsktra(G); } int main(){ int m,n; while(cin>>m>>n&&m!=0&&n!=0){//每次处理一行数据 Calculate(m,n); } return 0; }

4012最长的最短路径的求解

相关推荐