医院设置floyd算法求短路径.pptx

设有一棵二叉树（如下图，其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2*20+2*40=136；若医院建在3处，则距离和=4*2+13+20+40=81……【输入格式】输入文件名为hospital.in，其中第一行一个整数n，表示树的结点数（n=100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接，为0表示无链接。【输出格式】输出文件名为hospital.out，该文件只有一个整数，表示最小距离和。【样例输入】51323400124520004000【样例输出】81医院设置

我们从最简单的说起，如果给你下面一张图，怎么样才能把这张图给存储到计算机中呢？从图中我们可以看到，对这样一个图结构来说，最引人注目的不就是图中的顶点和边了，就是这两个元素构成了一个图，图也表示了两个或者多个顶点之间是否有关系。介绍完了图“长”这样以后，我们来讨论下图的种类；图分为有向图和无向图两种，顾名思义，就是表示图中的边是否有方向。邻接存储

接下来我们说说如何用邻接矩阵把这两种图存储起来。首先对于无向图来说，我们首先要让计算机知道我们想要存储的图有几个顶点，有几条边，这很重要，所以我们在程序的开始就需要n（顶点）和e（边数）。对于后面这个图，仔细想想的确能够表示前面这个图，1表示存在边，0表示不存在边；看矩阵，比如（1，1），表示1顶点和1顶点没有关系（在数据结构中，我们认为顶点自己的自环不算存在关系，当然在离散数学中是可以的），再比如（1，2）表示1和2顶点有关系，比如（3，4），表示3，4两个顶点有边。比如有4个顶点，那就生成4x4的矩阵。

接着我们说说有向图，其实理解了无向图，其实有向图也就很容易了，不就是多个方向嘛。此时我们就要注意了对于有向图中，矩阵样子是和无向图差不多的，但是理解不一样；比如（1，2），在无向图中表示顶点1和顶点2有关系，而1，2在有向图指顶点1指向顶点2有一条边，这里要分清楚集合和序偶的概念。所以，自然有向图的矩阵就不一定对称了。

弗洛伊德(Floyd)算法是一种用于寻找给定的加权图中顶点间最短路径的算法。通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。从任意节点i到任意节点j的最短路径不外乎2种可能：1)直接从节点i到节点j，2)从节点i经过若干个节点k到节点j。假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的最短路径的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。接下来开始，对矩阵S进行N次更新。第1次更新时，如果a[i][j]的距离a[i][0]+a[0][j](a[i][0]+a[0][j]表示i与j之间经过第1个顶点的距离)，则更新a[i][j]为a[i][0]+a[0][j]。同理，第k次更新时，如果a[i][j]的距离a[i][k]+a[k][j]，则更新a[i][j]为a[i][k]+a[k][j]。更新N次之后，操作完成！单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。弗洛伊德(Floyd)算法

以下图G4为例，来对弗洛伊德进行算法演示。

这是一道简单的二叉树应用问题，问题中的结点数并不多，数据规模也不大，采用邻接矩阵存储，用Floyed法求出任意两结点之间的最短路径长，然后穷举医院可能建立的n个结点位置，找出一个最小距离的位置即可。当然也可以用双链表结构或带父结点信息的数组存储结构来解决，但实际操作稍微麻烦了一点。【后记】在各种竞赛中经常遇到这样的问题：N-1条公路连接着N个城市，从每个城市出发都可以通过公路到达其它任意的城市。每个城市里面都有一定数量的居民，但是数量并不一定相等，每条公路的长度也不一定相等。X公司（或者是政府）决定在某一个城市建立一个医院/酒厂/游乐场……，问：将它建在哪里，可以使得所有的居民移动到那里的总耗费最小？这种题目都是本题的“变型”，一般称为“树的中心点问题”。除了简单的穷举法外，还有更好的时间复杂度为O(n)的算法，我们讲在后面的课时中继续讨论。算法分析