第12关：最长的最短路径的求解

Question

任务描述
设计一个算法，求图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。

测试说明
平台会对你编写的代码进行测试：

测试输入：
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
2
4
8

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
#define MaxInt 32767
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
    int vexnum,arcnum;    //图的当前顶点数和边数
    int vexs[MVNum];        //顶点表
    int arcs[MVNum][MVNum];    //邻接矩阵
}AMGraph;
int CreateUDN(AMGraph &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法，创建无向网G
    G.vexnum=vexnum;     //输入总顶点数
    G.arcnum=arcnum;     //输入总边数
    if(G.vexnum>MVNum) return ERROR;  //超出最大顶点数则结束函数
    int i,j,a,b,c;
    for(i=1;i<=G.vexnum;i++)
        G.vexs[i]=i;
    for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵，边的权值均置为极大值
        for(j=1;j<=G.vexnum;j++)
            G.arcs[i][j]=MaxInt;
    for(i=0;i<G.arcnum;i++)   //顶点a和顶点b之间有一条长度为c的路
    {
        cin>>a>>b>>c;
        G.arcs[a][b]=c;
        G.arcs[b][a]=c;
    }
    return OK;
}
void ShortPathMAX(AMGraph G,int v0)
{//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点
/**************begin************/








    /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        AMGraph G;
        CreateUDN(G,n,m);    //创建无向网G
        int v;
        cin>>v;
        ShortPathMAX(G,v);   //最长的最短路径的求解
    }
    return 0;
}

Answer 1

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7685051