关于数据结构的最短路径设计问题

Question

已知有向图，图中各顶点代表居民区，有向边代表交通路线。权表示路程。要在居民区建立一家医院。要求各居民区到医院的路径尽可能短，请设计医院建在哪个居民区比较合适。

（1）问题分析
图中各顶点代表居民区，边上的权代表各居民区的路程。要解决选地址问题，必须确定最短路径。求各顶点到其它顶点的最短路径，并求和。对各居民区的最短路径和进行比较，然后确定选址。
（2）问题的实现
采用单源最短路径算法，对各居民区的最短路径进行计算。
求设计的c++代码

Answer 1

#include<iostream.h>
const int n=5;
const int e=10;
int sum1[5];
int sum2[5];
int sum3[5];
int j=0;
int min;
int l;
#define max 32767
class Graph
{
public:
int arcs[n+1][n+1];
int a[n+1][n+1];
int path [n+1][n+1];
void floyd(Graph &t,const int n);
};
void Graph::floyd(Graph &t,const int n)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
t.a[i][j]=t.arcs[i][j];
if((i!=j)&&(a[i][j]<max))
t.path[i][j]=i;
else t.path[i][j]=0;
}
for(int k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
if(t.a[i][k]+t.a[k][j]<t.a[i][j])
{
t.a[i][j]=t.a[i][k]+t.a[k][j];
t.path[i][j]=t.path[k][j];
}
}

cout<<'\n'<<'\n';
for(i=0;i<n;i++)
{

for(j=0;j<n;j++)
cout<<t.arcs[i][j]<<'\t';
cout<<'\n';
}
cout<<'\n'<<'\n';
for(i=0;i<n;i++)
{
sum1[i]=0;
for(int j=0;j<n;j++)
{
if(i!=j)
{
cout<<t.a[i][j]<<":";
int next=t.path[i][j];
cout<<j;
while(next !=i)
{
cout<<"<--"<<next;
next=t.path[i][next];
}
cout<<"<--"<<i<<endl;
sum1[i]+=t.a[i][j];
}

}

cout<<i<<"到所有点的路径和为："<<sum1[i]<<endl;
}
for(i=0;i<n;i++)
{
sum2[i]=0;
for(j=0;j<n;j++)
{
if(i!=j)
{
cout<<t.a[j][i]<<":";
int next=t.path[j][i];
cout<<i;
while(next !=j)
{
cout<<"<--"<<next;
next=t.path[j][next];
}
cout<<"<--"<<j<<endl;
}
sum2[i]+=t.a[j][i];
}
cout<<"所有的点到"<<i<<"路径和为："<<sum2[i]<<endl;
}
for(int o=0;o<n;o++)
{
sum3[o]=sum1[o]+sum2[o];
cout<<o<<"的往返路径的和为："<<sum3[o]<<endl;
}
min=sum3[0];
for(int h=0;h<n;h++)
{
if(sum3[h]<=min)
{

min=sum3[h];
l=h;
}

}
cout<<"比较可得最短的路径为"<<min<<" 应该在点 "<<l<< " 哪里建立医院。"<<endl;

}
void main()
{
Graph t;int i,j,w;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j)t.arcs[i][j]=0;
else t.arcs[i][j]=max;
for(int k=0;k<e;k++)
{
cin>>i>>j>>w;
t.arcs[i][j]=w;
}

t.floyd(t,n);
}

Answer 2

用floyd算法计算出每个点之间的最短路径，再选一个离每个点都近的（单点与其他各点路径值相加最小的）作为医院。

个人认为应该是这样，供参考。本回答被网友采纳