社区医院选址问题

约定不等于承诺〃 2022-05-23 13:38 195阅读 0赞

### 问题描述 ###

n个社区之间的交通图用有向加权图表示，先要从这n个社区中选择一个社区建立一所医院，问这所医院应建在那个社区，能使所有的社区都离这家医院比较近（能使离医院最远的社区到医院最近）或能使所有的社区达到医院的距离之和达到最小。

### 问题分析 ###

关键就是要使所有的社区到达医院的距离之和最小。有两种办法，一种是直接运用弗罗伊得算法，求出任意两点之间的最短路径在求和。还有一种就是对每个点用dijkstra方法求出带其他点的最短路径之和然后在比较选最小的。在这里我用了第二种方法。

### 具体实现 ###

void linkedDgraph1::shortPaths(int sourceVertex,int *distanceFromSource,int *predecessor)
    {
        graphChain<int> newReachableVertices;
        for(int i=1;i<=num1;i++)
        {
            distanceFromSource[i]=getWeight(sourceVertex,i);
            if(distanceFromSource[i]==10000)//10000代表着不存在此边 
              predecessor[i]=-1;
            else
            {
                predecessor[i]=sourceVertex;
                newReachableVertices.insert(i,0);//插入此节点 
            }
        }
         distanceFromSource[sourceVertex]=0;
              predecessor[sourceVertex] =0;
              while(!newReachableVertices.empty())
              {  //找到链表中的距离最小的点 
                 graphNode<int> *p=newReachableVertices.first();
                 int v=p->element;
                 p=p->next;
                 while(p!=NULL)
                 {
                    int w=p->element;
                    p=p->next;
                    if(distanceFromSource[w]<distanceFromSource[v])
                      v=w;
    
                 }
                 newReachableVertices.erase(v);
                 for(int j=1;j<=num1;j++)//检查最短距离是否有更新 
                 {
                    if(getWeight(v,j)!=10000&&predecessor[j]==-1||distanceFromSource[j]>distanceFromSource[v]+getWeight(v,j))
                    {
    
                        distanceFromSource[j]=distanceFromSource[v]+getWeight(v,j);
                         if(predecessor[j]==-1)
                           newReachableVertices.insert(j,0);
                          predecessor[j]=v;                     
                     }
                 }
              }   
    }

int n=6;string nn="请输入社区数：范围为（0-1000）";
       do
       { 
         cin.sync();
         cin.clear();
         cout<<nn;
        cin.sync();
         cin.clear();
         cin>>n;
         if(cin.fail()||n<0||n>1000)
          cout<<"请重新输入"<<endl;
       }while(cin.fail()||n<0||n>1000);
         int *sum=new int[n];
         for(int i=0;i<n;i++)
         sum[i]=0;
         linkedDgraph1 g(n);
         /*g.insertEdge(1,3,2);//书上的例子 g.insertEdge(1,2,4); g.insertEdge(1,5,8); g.insertEdge(3,4,1); g.insertEdge(2,4,4); g.insertEdge(2,5,5); g.insertEdge(4,5,3); //有环的例子 g.insertEdge(1,2,3); g.insertEdge(1,3,6); g.insertEdge(3,4,10); g.insertEdge(2,4,5); g.insertEdge(2,5,5); g.insertEdge(4,1,5); g.insertEdge(1,4,5);*/
          int number=0;//边数 
          string nb="请输入边数: 范围为（0-2000）";
    do
       { 
         cin.sync();
         cin.clear();
         cout<<nb;
        cin.sync();
         cin.clear();
         cin>>number;
         if(cin.fail()||number<0||number>2000)
          cout<<"请重新输入"<<endl;
       }while(cin.fail()||number<0||number>2000); 
        int a,b,c;
        cout<<"请依次输入各路径:"<<endl; 
        srand((unsigned)time(NULL));
        for(int i=0;i<number;i++)
        {   a=rand()%n;
            b=rand()%n;
            c=rand()%10000;
            //cin>>a>>b>>c;
            cout<<a<<" "<<b<<" "<<c<<" ";
            g.insertEdge(a,b,c);
         } 
         for(int j=1;j<=n;j++)
         { 
           int *aa=new int[n];
           int *bb=new int[n];
           g.shortPaths(j,aa,bb);
           for(int i=1;i<=n;i++)
           {
       if(aa[i]==10000)
             {
               sum[j]=10000;
               break;   
             }   
            cout<<aa[i]<<" ";
            sum[j]+=aa[i];
           }
          cout<<"最短路径之和为："<<sum[j]<<endl;  
         }
         int min=sum[1];int minIndex=1;
         for(int i=1;i<=n;i++)
         {
            if(sum[i]<min)
               {
                min=sum[i];
                minIndex=i;
               }
         }
         if(min==10000)
         cout<<"不存在合适的社区";
         else
         cout<<"点应该设在"<<" "<<minIndex;

### 输出结果： ###

![社区图][70]  
![70 1][]

### 说明 ###

所用图结构为加权有向图，用邻接链表实现的。

[70]: /images/20220523/30e2cfec9bdc4477abed35248703f693.png
[70 1]: /images/20220523/05c27f19421b4cc0971fb6fa964c9a0e.png