图论的问题,求图上一点,可以是顶点,也可以是边上一点,使所有顶点到该点的距离的和最短?

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/05 07:23:48

图论的问题,求图上一点,可以是顶点,也可以是边上一点,使所有顶点到该点的距离的和最短?
Dijkstra和Floyd算法只是算顶点到顶点的最短路径的问题,这个问题不适用啊

1.用Floyd算法可以得到的是每两个点之间的最短距离.
2.对于每个点,把其到其它点的最短距离加和.此即为此点到其它顶点最小距离和.
3.于是最小值对应的点就是所要求的点.
4.有问题再问我吧,没问题就多加点分吧...
再问：我想找的是在边上的一点，不是现有的某点啊。 Floyd算法算出的是点之间的最短距离，但是不包括边上的某一点。所以上面的答案不满足题设啊。
再答：你原来是这个意思啊，那不好意思哈，我理解错了... 这样的话，如果它不是一个可平面图，那边上的点到点之间的距离不能定义了，因此按照你题目的意思，它应该是一个可平面图。这样我们可以证明，最优解一定可以在顶点上取得的。证明如下：若最优点是AB边上的C点，那么C点到达其它所有点的最短距离路要么经过A，要么经过B，假设经过A点的次数为m，B点的次数为n。若m=n，则A点与B点也为最优点。（这点你能想明白吧？）若m>n，那么A点比C点更优（若不明白，画个图哈。），矛盾，不成立，故m=n。于是m=n是一定成立的。即A，B，C都为最优点。若没有问题多加点分吧...若有问题，欢迎继续讨论.......
再问：是可平面图。我刚开始也是这么想的，假设所有点到某一点距离之和为F（x），则AB边上的点是以F(A)和F(B)为边界的线性函数，最小值一定在两边取到。但是后来想到有可能目标点C在AB上变化时，原本经过A点到达C的较近点改为经过B点到达C了，这样F(X)在AB中间变化时就会存在几个不连续点（由变化过程中改变路径的点决定数量），这样F(x)在A，B上的最小值就很难确定了。有没有什么解决路径可能改变的情况下确定最短距离的好方法？
再答：首先你对我上面的证明没有疑问吧？其次F(x)不一定是线性函数，但一定是连续的，这个毫无疑问。这个其实很明显的，C在AB上变化时，原本经过A点到达C的较近点改为经过B点到达C了，这个不是突变的，一定会先到某一点使得，通过A和通过B的距离是一样的...然后再变换过去的......

图论的问题,求图上一点,可以是顶点,也可以是边上一点,使所有顶点到该点的距离的和最短? 三角形平面内有一点,该点到三角形三个顶点的距离和最短,则该点是三角形的在锐角三角形中,求一点P,使P到此三角形三个顶点的距离和最短,求点P的位置在锐角三角形ABC中,找一点p到三个顶点的距离之和最短在三角形内部找一点,使它与三个顶点的距离之和最短? 三角形三条边的垂直平分线相交于一点,并且这一点到三个顶点的距离相等（且距离最短）,为什么距离最短求三角形面积的最小值一个90°角内部一点,到角的两边距离分别是3和5,过该点的直线和角的两边分别相交,两个交点和角的顶点求一点到一平面的三点距离的和最短,点的位置平面上找一点,使到正方形四个顶点距离相等的点有几个, 怎样在一个正方形的对角线上找一点,使他到正方形三个顶点距离最短?方法是什么?（最后什么数学思想）设P点是三角形ABC内一点,求：P到三角形ABC三顶点的距离和三角形周长之比的取值范围锐角三角形中一点到三个顶点的距离相等,那么这个三角形是等边三角形吗?