C++编程实现医院选址问题
发布网友
发布时间：2022-05-10 13:14
共5个回答
热心网友
时间：2023-10-10 01:01
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)
{biaoji2+=dist[i];biaoji1++;}
else
{
cout<<"和为："<<" "<<biaoji2;
biaoji1=0;biaoji2=0;
}
}
else
cout<<"从"<<v<<"到"<<i<<"不存在的路径"<<endl;
}
}
void Dijkstra(MGraph g,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for(i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF) path[i]=v;
else path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis=INF;
for(j=0;j<g.n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=0;j<g.n;j++)
{
if(s[j]==0)
{
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
}
Dispath(dist,path,s,g.n,v);
}
//弗洛伊德算法
void Ppath1(int path[][MAXV],int i,int j)
{
int k;
k=path[i][j];
if(k==-1) return;
Ppath1(path,i,k);
cout<<k;
Ppath1(path,k,j);
}
void Dispath1(int A[][MAXV],int path[][MAXV],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j) continue;
if(A[i][j]==INF)
{
if(i!=j)
cout<<"从"<<i<<"到"<<j<<"不存在路径"<<endl;
}
else
{
cout<<"从"<<i<<"到"<<j<<"的最短路径长度为:"<<A[i][j]<<" ";
cout<<i;
Ppath1(path,i,j);
cout<<j<<endl;
}
}
}
}
void Floyd(MGraph g)
{
int A[MAXV][MAXV],path[MAXV][MAXV];
int i,j,k;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
}
for(k=0;k<g.n;k++)
{
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
if(A[i][j]>A[i][k]+A[k][j])
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
}
Dispath1(A,path,g.n);
}
//主函数
int main()
{
int i,j,n;
MGraph g;
cout<<"请输入带权有向图的顶点个数：";//6
while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/)
{
cout<<"请输入带权有向图的邻接矩阵："<<endl;
/*
0 5 32767 7 32767 32767
32767 0 4 32767 32767 32767
8 32767 0 32767 32767 9
32767 32767 5 0 32767 6
32767 32767 32767 5 0 32767
3 32767 32767 32767 1 0
*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
//scanf("%d",&g.edges[i][j]);
cin>>g.edges[i][j];
}
}
g.n=n;
cout<<"采用狄克斯特拉算法得到的最短路径为："<<endl;
for(i=0;i<n;i++) Dijkstra(g,i);
cout<<endl;
cout<<"采用弗洛伊德算法得到的最短路径为："<<endl;
Floyd(g);
cout<<endl;
cout<<"请输入带权无向图的顶点个数：";
}
return 0;
}
2.代码如下
#include <iostream>
using namespace std;
int INFTY=32767;
template<class T>
class Graph
{
public:
virtual void Insert(int u,int v,T& w)=0;
virtual void Remove(int u,int v)=0;
virtual bool Exist(int u,int v)=0;
virtual int Vertices()const {return n;}
protected:
int n,e;
};
template <class T>
class MGraph:public Graph<T>//邻接矩阵存储图
{
public:
MGraph();
~MGraph();
void Build_Graph();
void Insert(int u,int v,T& w);
void Remove(int u,int v);
bool Exist(int u,int v);
void Floyd(T**&d,int**&path);
int num;
protected:
T**a;
T noEdge;
};
template <class T>
void MGraph<T>::Build_Graph()//建图
{
cout<<"请输入顶点的个数："<<endl;
int C_num;
cin>>C_num;
num=n=C_num;e=0;noEdge=INFTY;
a=new T*[n];
for(int k=0;k<n;k++){
a[k]=new T [n];
for(int j=0;j<n;j++)a[k][j]=noEdge;
a[k][k]=0;
}
cout<<"建立村庄编号为1--"<<C_num<<"的图"<<endl;
for(int i=0;i!=C_num;i++)
for(int j=i+1;j!=C_num;j++)
{
int w;
cout<<"请输入村庄"<<i+1<<"与村庄"<<j+1<<"之间的权值：";
cin>>w;
Insert(i,j,w); //向图中添加权值为W的边
cout<<i<<"--->"<<j<<":"<<a[i][j]<<endl;
}
cout<<"*********************************************************************"<<endl;
cout<<"已建立村庄编号为1--"<<C_num<<"的图:"<<endl;
cout<<"**********************************"<<endl;
cout<<" \t\t";
for(int b=1;b<=C_num;b++){
cout<<b<<"\t";
}
cout<<endl;
}
template <class T>
MGraph<T>::MGraph()
{
Build_Graph();
}
template <class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}
template <class T>
bool MGraph<T>::Exist(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false;
return true;
}
template <class T>
void MGraph<T>::Insert(int u,int v,T &w)
{
a[u][v]=w;a[v][u]=w;e++;
}
template <class T>
void MGraph<T>::Remove(int u,int v)
{
a[u][v]=noEdge;e--;
}
template <class T>
void MGraph<T>::Floyd(T**&d,int**&path)//所有顶点之间的最短路径
{
int i,j,k;
d=new T*[n];path=new int*[n];
for(i=0;i<n;i++){
d[i]=new T[n];path[i]=new int[n];
for(j=0;j<n;j++){
d[i][j]=a[i][j];
if(i!=j&& a[i][j]<INFTY)path[i][j]=i;
else path[i][j]=-1;
}
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]+d[k][j]<a[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
int main()
{
MGraph<int> Hospital;
int **d,**path;
int i,j,n;
n=Hospital.num;
Hospital.Floyd(d,path);
int *sum=new int[n];
cout<<endl;
for(i=0;i!=n;i++)//输出矩阵
{
cout<<i+1<<"\t\t";
sum[i]=0;
for(j=0;j!=n;j++)
{
sum[i]+=d[i][j];
cout<<d[i][j]<<"\t";
}
cout<<endl;
}
cout<<"*********************************************************************"<<endl;
int min=0;
for(i=0;i!=n;i++)
{
cout<<i+1<<"村庄："<<sum[i]<<endl;
if(sum[min]>sum[i])//判断最短路径
min=i;
}
cout<<"医院应在编号为"<<min+1<<"的村庄"<<endl;
for(i=0;i<n;i++)
{
delete[]d[i];
delete[]path[i];
}
delete[]d;
delete[]path;
return 0;
}
热心网友
时间：2023-10-10 01:02
using namespace std;
#define MaxInt 10000//最大数
const int MaxNumEdges=50;
const int MaxNumVertices=10; //最大顶点数
class Graph{
private:
int vNum;//当前顶点数
int eNum;//当前边数
int Vertex[MaxNumVertices];//顶点数组
int Edge[MaxNumVertices][MaxNumVertices];//边数组
bool GetVertexPos(const int &vertex,int &i);//给出顶点vertex在图中的位置
public:
Graph(const int sz= MaxNumEdges);//构造函数
bool FindVertex(const int &vertex);
bool InsertVertex(const int & vertex);//插入一个顶点vertex
bool InsertEdge(const int v1,const int v2,const int weight);//插入一条边(v1,v2),该边上的权值为weight
void Hospital();//医院选址函数
};
Graph::Graph(const int sz): vNum(0), eNum(0)//构造函数
{
int n,e;
int name,tail,head;
int weight;
for(int i=0;i<sz;i++)
for(int j=0;j<sz;j++)
{
if(i==j)
Edge[i][j]=0;//顶点到自身权值为0
else
Edge[i][j]=10000;//邻接矩阵初始化为最大值
}
cout<<"请输入顶点数,注意本程序最多为10个。\n";
cin>>n;
cout<<"请依次输入顶点名称:\n";
for(i=0;i<n;i++)//依次输入顶点，插入图中
{
cin>>name;
InsertVertex(name);
vNum++;
}
cout<<"请输入边数:\n";
cin>>e;
cout<<"以下输入边信息。\n";
for(i=0;i<e;i++){
cout<<"请输入第"<<i+1<<"边头顶点：\n";
cin>>head;
cout<<"请输入该边尾顶点：\n";
cin>>tail;
cout<<"请输入该边权值：\n";
cin>>weight;
if(!InsertEdge(head,tail,weight)){
cout<<"不存在该边，请重输！\n";
continue;
}
}
}
bool Graph::FindVertex(const int& vertex){//给出顶点vertex在图中的位置
for (int i = 0; i < vNum; i++)
if (vertex == Vertex[i])
return true;
return false;
}
bool Graph:: GetVertexPos(const int &vertex,int &i){//给出顶点vertex在图中的位置
for (i = 0; i < vNum; i++)
if (vertex == Vertex[i])
return true;
return false;
}
bool Graph::InsertVertex(const int & vertex){//插入一个顶点vertex
if (FindVertex(vertex))
return false;
Vertex[vNum] = vertex;
return true;
}
bool Graph::InsertEdge(const int v1,const int v2,const int weight){
//插入一条边(v1,v2),该边上的权值为weight
int k=0,j=0;
if(GetVertexPos(v1,k) && GetVertexPos(v2,j)){
Edge[k][j]=weight; eNum++;
Edge[j][k]=weight; eNum++;
return true;
}
else
return false;
}
void Graph::Hospital()
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{
int k,i,j,s;
for (k=0;k<vNum;k++) //求任意两顶点间的最短路径
for (i=0;i<vNum;i++)
for (j=0;j<vNum;j++)
if (Edge[i][k]+Edge[k][j]<Edge[i][j])
Edge[i][j]=Edge[i][k]+Edge[k][j];
int m=MaxInt; //设定m为机器内最大整数。
cout<<"********************************************"<<endl;
//以下为求各村离医院最近的医院选址
int min=MaxInt ; //设定机器最大数作村庄间距离之和的初值。
k=0; //k设医院位置。
for (j=0;j<vNum;j++){
m=0 ;
for (i=0;i<vNum;i++) m=m+Edge[i][j]; //顶点到其它顶点最短距离的距离之和
if (min>m) { min=m ;k=j;} //取顶点间的距离之和的最小值。
}//for
cout<<"各村离医院最近的医院选址,要建医院的村庄号:"<<k+1<<'\n'; //输出要建医院的村庄号
//输出要建医院的村庄号及离医院最远的村庄到医院的距离
for(j=0;j<vNum;j++)
if(j!=k)
cout<<"该村庄离"<<j+1<<"村庄最短距离为:"<<Edge[k][j]<<'\n';
}//算法结束
int main(int argc, char* argv[])
{
Graph Town(MaxNumVertices);
Town.Hospital();
return 0;
}
参考资料：非非
热心网友
时间：2023-10-10 01:02
热心网友
时间：2023-10-10 01:03
热心网友
时间：2023-10-10 01:04
