注册 登录
编程论坛 → C++教室

麻烦大家帮忙检查下作业，帮忙调试指正下

longyushen 发布于 2012-01-01 18:21， 715 次点击
只有本站会员才能查看附件，请 登录
医院选址问题
【问题描述】
n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
【基本要求】
(1) 建立模型，设计存储结构；
(2) 设计算法完成问题求解；
(3) 分析算法的时间复杂度。

******************具体看附件************************
程序代码：
#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;
}
2 回复
#2
longyushen2012-01-02 14:06
怎么没人理的？
#3
longyushen2012-01-03 13:45
正确代码分享
程序代码：
#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;
}

 
1
©2025, BC-CN.NET
电脑版