选址问题

选址问题是指为一个或者几个服务设置在一定区域内选定他的位置，是的某一指标达到最优值。选址问题根据这些设置需要的指标的要求可以大致分为两类：

• 中心问题
• 重心问题

中心问题

中心问题指的是一些紧急公共设施如医院、消防站的选址，要求网路中最远的被服务对象离服务站的距离尽可能小。‘因此我们可以使用Floyd算法求得每组两点之间的最短距离。在选择某一行最大值的与其他行进行比较。选择最大值的最小值。

import com.dwx.passage2.Floyd;

import java.util.Scanner;

public class zhongxinwenrti {
    public static void main(String[] args) {
        //我们这边使用的是无向图
        Scanner scanner = new Scanner(System.in);
        int inf = 99999999;
        //m 表示点数 n表示边数
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int x, y;
        double l;
        //创建数组
        double[][] a = new double[m][m];
        //对数组初始化
        int i, j;
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                if (i == j) {
                    a[i][j] = 0;
                } else {
                    a[i][j] = inf;
                }

            }
        }
        //导入边数据
        for (i = 1; i <= n; i++) {
            //x表示横坐标 y表示纵坐标 l表示长度
            x = scanner.nextInt();
            y = scanner.nextInt();
            l = scanner.nextDouble();
            //这里我们使用的是无向图
            a[x][y] = l;
            a[y][x] = l;
        }
        for (double[] ints : a) {
            for (double anInt : ints) {
                if (anInt == inf) {
                    System.out.print("inf" + "\t");
                } else {
                    System.out.print(anInt + "    ");
                }
            }
            System.out.println();
        }

        System.out.println("=====================");
            //调用Floyd算法求得 两两点之间的最短路径
            Floyd floyd = new Floyd();
            floyd.setE(a);
            floyd.floyd();
            double[][] e = floyd.getE();

            for (double[] ints1 : e) {
                for (double anInt : ints1) {
                    if (anInt == inf) {
                        System.out.print("inf" + "\t");
                    } else {
                        System.out.print(anInt + "    ");
                    }
                }
                System.out.println();
            }
        }
    }

程序输出:

0.0    3.0    5.0    10.0    7.0    5.5    7.0    
3.0    0.0    2.0    7.0    4.0    2.5    4.0    
5.0    2.0    0.0    5.0    2.0    4.5    6.0    
10.0    7.0    5.0    0.0    3.0    7.0    8.5    
7.0    4.0    2.0    3.0    0.0    4.0    5.5    
5.5    2.5    4.5    7.0    4.0    0.0    1.5    
7.0    4.0    6.0    8.5    5.5    1.5    0.0    

可以看到 我们的最短路径矩阵，每一行的最大值中的最小值是在第3行 因此建设在V3点

重心问题

某些设备如工厂，学校，邮局等不是紧急单位，但是和民生息息相关的公共设置，需要选择要求到每个点的距离中的最短，才能保证有条件的公平与便利。

解题思路：利用弗洛伊德算法，求得两点之间最短距离的矩阵，获得矩阵的各行的参数的相加。找到最小的。

程序实现：

import com.dwx.passage2.Floyd;

import java.util.Scanner;

public class Zhongxinwenti {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int inf = 99999999;
        //创建矩阵
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        double[][] a = new double[m][m];
        //矩阵初始化
        int i,j,k,x,y;
        double l;
        for (i=0;i<m;i++){
            for (j=0;j<m;j++){
                if (i==j){
                    a[i][j] = 0;
                }else {
                    a[i][j] = inf;
                }
            }
        }
        //读入数据
        for (i=1;i<=n;i++){
            x = scanner.nextInt();
            y = scanner.nextInt();
            l = scanner.nextDouble();
            a[x][y] = l;
            a[y][x] = l;
        }
        //调用弗洛伊德算法求解
        Floyd floyd = new Floyd();
        floyd.setE(a);
        floyd.floyd();
        double[][] e = floyd.getE();
        for (double[] doubles : e) {
            for (double aDouble : doubles) {
                System.out.print(aDouble+"\t");
            }
            System.out.println();
        }
        System.out.println("=========================================");
        double sum = 0;
        for (double[] doubles : e) {
            sum = 0;
            for (double aDouble : doubles) {
                sum = sum + aDouble;
            }
            System.out.println(sum);
        }


    }
}

输出：

0.0	3.0	5.0	8.0	7.0	7.0	8.5	
3.0	0.0	2.0	5.0	4.0	4.0	5.5	
5.0	2.0	0.0	3.0	2.0	6.0	7.5	
8.0	5.0	3.0	0.0	1.0	5.0	6.5	
7.0	4.0	2.0	1.0	0.0	4.0	5.5	
7.0	4.0	6.0	5.0	4.0	0.0	1.5	
8.5	5.5	7.5	6.5	5.5	1.5	0.0	
=========================================
38.5
23.5
25.5
28.5
23.5
27.5
35.0

Process finished with exit code 0

由此可知 建在v2或者v5都可以

Donate