Floyd算法應用-醫院選址問題

1)問題描述

n個村莊之間的交通圖可以用有向網圖來表示，圖中邊<v_i, v_j>上的權值表示從村莊i到村莊j的道路長度。現在要從這n個村莊中選擇一個村莊新建一所醫院，問這所醫院應建在哪個村莊，才能使所有的村莊離醫院都比較近？

2) 基本要求

(1) 建立模型，設計存儲結構；

(2) 設計算法完成問題求解；

(3) 分析算法的時間復雜度。

3) 設計思想

醫院選址問題實際是求有向圖中心點的問題。首先定義頂點的偏心度。

設圖G=（V，E），對任一頂點k，稱E(k)=max{d(i, k)}（i∈V）為頂點k的偏心度。顯然，偏心度最小的頂點即為圖G的中心點。

如圖3(a)所示是一個帶權有向圖，其各頂點的偏心度如圖(b)所示。

?

4)醫院選址問題的算法用偽代碼描述如下：

1．對加權有向圖，調用Floyd算法，求每對頂點間最短路徑長度的矩陣；

2．對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度；

3．具有最小偏心度的頂點即為所求。

5)代碼附錄

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 1000000
#define MAX_VERTEX_NUM 20

//定義弧的權值信息
typedef struct Arccell
{
    int adj; //權值
} Arccell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //圖的鄰接矩陣
//定義結點信息
typedef struct VertexInfo
{
    char name[20];//結點[村莊]名稱
    int position;//定點編號
} VertexInfo;
//圖的結構
typedef struct Mgraph
{
    VertexInfo vexs[MAX_VERTEX_NUM];//頂點數組
    AdjMatrix arcs;//鄰接矩陣
    int vernum,arcnum;//分別指定頂點數和邊數
} Mgraph;


//對圖的初始化
Mgraph initgraph()
{
    Mgraph c;
    printf("請輸入該圖的頂點個數和弧的個數：\n");
    printf("頂點個數：");
    scanf("%d",&c.vernum);
    printf("弧的個數：");
    scanf("%d",&c.arcnum);
    //依次設置頂點編號
    for(int i=0; i<c.vernum; i++)
    {
        c.vexs[i].position=i;
    }
    //依次輸入各頂點信息
    /*
    strcpy(c.vexs[0].name,"a");
    strcpy(c.vexs[1].name,"b");
    strcpy(c.vexs[2].name,"c");
    strcpy(c.vexs[3].name,"d");
    strcpy(c.vexs[4].name,"e");

    */
    printf("\n請依次輸入各個村莊的名稱：\n");
    for(int i=0;i<c.vernum;i++)
    {
        printf("村莊%d:",i);
        scanf("%s",&c.vexs[i].name);

    }

    //依次設置各弧的信息
    for(int i=0; i<c.vernum; i++)
    {
        //先初始化鄰接矩陣,相同點設置為0，其他全部設置為INFINITY（無窮大）
        for(int j=0; j<c.vernum; j++)
        {
            c.arcs[i][j].adj=INFINITY;
            if(i==j)
            {
                c.arcs[i][j].adj=0;
            }
        }
    }
    //再依次輸入需要設置的權值
    int i,j,k;
    printf("請輸入需要設置的弧長及其兩端頂點[輸入3個0結束]：\n");
    while(scanf("%d%d%d",&i,&j,&k))
    {
        if(i==0&&j==0&k==0)
            break;
        c.arcs[i][j].adj=k;
    }
    /*
    c.arcs[0][1].adj=1;
    c.arcs[1][2].adj=2;
    c.arcs[2][3].adj=2;
    c.arcs[2][4].adj=4;
    c.arcs[3][1].adj=1;
    c.arcs[3][2].adj=3;
    c.arcs[4][3].adj=5;
    */
    return c;
}

//輸出鄰接矩陣
void printMatrix(Mgraph c)
{
    printf("該圖的鄰接矩陣如下所示：\n");
    int count=0;//用于計數
    for(int i=0; i<c.vernum; i++)
        for(int j=0; j<c.vernum; j++)
        {
            if(c.arcs[i][j].adj==INFINITY)
                printf("   #");
            else
                printf("%4d",c.arcs[i][j].adj);
            count++;
            if(count%c.vernum==0)
                printf("\n");
        }
}

void ShortestPath_Floyd(Mgraph G,int dis[][MAX_VERTEX_NUM])
{
    //用floyd算法求有向網G中各對定點v和w之間的最短路徑及其帶權長度dis[v][w]
    for(int v=0; v<G.vernum; v++)
        for(int w=0; w<G.vernum; w++)
        {
            //對各結點之間初始化已知距離
            dis[v][w]=G.arcs[v][w].adj;
        }

    for(int u=0; u<G.vernum; u++)
        for(int v=0; v<G.vernum; v++)
            for(int w=0; w<G.vernum; w++)
            {
                if(dis[v][u]+dis[u][w]<dis[v][w])
                {
                    //從v經u到w的路徑更短
                    dis[v][w]=dis[v][u]+dis[u][w];
                }
            }

}
//輸出距離矩陣
void printDis(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
{
    printf("\n經過Flyod算法之后各頂點之間的距離如下：\n");
    for(int i=0; i<G.vernum; i++)
    {
        for(int j=0; j<G.vernum; j++)
        {
            if(dis[i][j]>=1000000)
                printf("   #");
            else
                printf("%4d",dis[i][j]);

        }
        printf("\n");
    }
}

//得到偏心度degree[]數組
void getDegree(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM],int degree[])
{
    for(int i=0;i<G.vernum;i++)
    {
        int max=dis[0][i];
        for(int j=0;j<G.vernum;j++)
        {
            if(dis[j][i]>max)
                max=dis[j][i];
        }
        degree[i]=max;
    }
}



int main()
{
    printf("**********歡迎使用醫院選址系統*********\n");
    Mgraph c=initgraph();
    system("cls");

    //輸出鄰接矩陣
    getchar();
    printMatrix(c);

    //定義距離數組，調用Floyd算法得到結果
    int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    ShortestPath_Floyd(c,dis);

    //輸出各個頂點之間的距離矩陣
    getchar();
    printDis(c,dis);

    //存放偏心度數
    int degree[c.vernum];
    getDegree(c,dis,degree);

    //顯示各頂點的偏心度
    getchar();
    printf("\n各頂點的偏心度如下所示：\n");
    for(int i=0;i<c.vernum;i++)
    {
        if(degree[i]>=1000000)
            printf("   #\n");
        else
            printf("%4d\n",degree[i]);
    }

    //得到最小村莊的編號和名稱
    int num;
    int min=degree[0];
    for(int i=0;i<c.vernum;i++)
    {
        if(min>degree[i])
            min=degree[i];
    }

    for(int i=0;i<c.vernum;i++)
    {
        if(min==degree[i])
        {
            num=i;
            break;
        }
    }
    getchar();
    printf("\n偏心度最小的村莊編號：%4d\n",num);//輸出偏心度最小的村莊編號
    printf("醫院應該建立在村莊:   %4s \n",c.vexs[num].name);
    return 0;

}

6)測試結果

1.首先運行程序，出現如圖6.1所示。

?

　　　　　　　　 ?圖6.1? 程序運行開始界面

2.輸入頂點個數和邊的個數之后，會提示輸入村莊名稱，如圖6.2所示。

?

??????????????????????? 圖6.2 提示輸入村莊名稱界面

3.村莊名稱輸入結束之后，提示輸入邊的起始點和權值，如圖6.3所示。

?

?? ?????????????????????圖6.3 提示輸入邊相關信息的界面

4.輸入邊的信息，以輸入0 0 0結束，如圖6.4所示。

?

??????????????????????? 圖6.4 輸入邊相關信息界面

5.邊的信息輸入完成之后，回車得到鄰接矩陣，如圖6.5所示。

?

?????????????????????????? 圖6.5 鄰接矩陣表

6.繼續回車，得到距離矩陣，如圖6.6所示。

?

?????????????????????????? 圖6.6 距離矩陣表

7.回車，得到偏心度表，如圖6.7所示。

?

?????????????????????????? 圖6.7 各頂點偏心度

8.最后程序輸出醫院選址結果，如圖6.8所示。

?

???????????????????????????? 圖6.8 最終結果