UC知道关于图的最短路径问题
来源：百度知道 编辑：UC知道 时间：2024/09/26 00:29:20
医院选址问题
问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题．
谁能提供思路或者C++代码更好，谢谢各位大虾了，打的好愿意追加更多得分
问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题．
谁能提供思路或者C++代码更好，谢谢各位大虾了，打的好愿意追加更多得分
医院选址
1.
代码如下
#include <iostream>
using namespace std;
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉算法
void Ppath(int path[],int i,int v)
{
int k;
k=path[i];
if(k==v) return;
Ppath(path,k,v);
cout<<k;
}
int biaoji1=0,biaoji2=0;
void Dispath(int dist[],int path[],int s[],int n,int v)
{
int i;
for(i=0;i<n;i++)
{
if(i==v) continue;
if(s[i]==1)
{
cout<<"从"<<v<<"到"<<i<<"的最短路径为："<<dist[i]<<" ";
cout<<v;
Ppath(path,i,v);
cout<<i<<endl;
if(biaoji1!=5)
{biaoj