数学建模期末速成 最短路径

关键词：Dijkstra算法 Floyd算法

例题

已知有6个村庄，各村的小学生人数如表所列，各村庄间的距离如图所示。现在计划建造一所医院和一所小学，问医院应建在哪个村庄才能使最远村庄的人到医院看病所走的路最短？又问小学建在哪个村庄使得所有学生上学走的总路程最短？

村庄	$v_1$	$v_2$	$v_3$	$v_4$	$v_5$	$v_6$
小学生人数/个	50	40	60	20	70	90

一、 问题重述

在6个村庄构成的交通网络中，已知各村小学生人数及村庄间道路距离。现需解决两个优化问题：
​​医院选址​​：确定一个村庄建立医院，使得离医院最远村庄的就医路径最短。
​​小学选址​​：确定一个村庄建立小学，使得全体学生上学总路程最短。

二、 问题分析

​​医院选址问题​​属于​​最小化最大距离​​问题，需计算各候选点到其他所有点的最短距离中的最大值，再选择使该值最小的位置。

​​小学选址问题​​属于​​加权最短路径和​​问题，需计算各候选点到所有生源村的加权距离和（权重为各村学生数），选择总和最小的位置。

三、 符号说明

符号	含义	单位
$V$	村庄集合 {$v_1,...,v_6$}	-
$E$	边集合（道路连接关系）	-
$W$	邻接矩阵（道路距离）	-
$d(i,j)$	村庄 $v_i$ 到 $v_j$ 的最短距离	-
$s_i$	村庄 $v_i$ 的学生人数	-

四、 模型假设

1. 道路网络为无向图，距离对称
2. 最短路径计算不考虑交通拥堵等动态因素
3. 学生人数固定且全部就近入学

五、 模型建立与求解

模型建立：

1. 图论建模
构造赋权图 ，邻接矩阵为：
$$W=\left[\begin{array}{cccccc}0& 2& 7& \infty & \infty & \infty \\ 2& 0& 4& 6& 8& \infty \\ 7& 4& 0& 1& 3& \infty \\ \infty & 6& 1& 0& 1& 6\\ \infty & 8& 3& 1& 0& 3\\ \infty & \infty & \infty & 6& 3& 0\end{array}\right]$$

2. 最短路径计算
应用Floyd算法求得全源最短距离矩阵 ：
$$d=\left[\begin{array}{cccccc}0& 2& 6& 7& 8& 11\\ 2& 0& 4& 5& 6& 9\\ 6& 4& 0& 1& 2& 5\\ 7& 5& 1& 0& 1& 4\\ 8& 6& 2& 1& 0& 3\\ 11& 9& 5& 4& 3& 0\end{array}\right]$$
3. 医院选址分析
计算各列最大值：
最大值向量 = $[11,9,6,7,8,11]$
最小值6对应的 ​ $v_3$ 为最优选址。

4. 小学选址分析
计算加权总路程：
总路程向量 = $[2130,1670,1070,1040,1050,1500]$
最小值1040对应的 ​$v_4$ 为最优选址。

例题求解代码

import numpy as np
import networkx as nx# 初始化参数
n = 6
node = ['v' + str(i) for i in range(1, n+1)]
students = [50, 40, 60, 20, 70, 90]# 构建邻接矩阵
A = np.zeros((n, n))
A[0, [1, 2]] = [2, 7]        # v1连接v2(2),v3(7)
A[1, [2, 3, 4]] = [4, 6, 8]  # v2连接v3(4),v4(6),v5(8)
A[2, [3, 4]] = [1, 3]        # v3连接v4(1),v5(3)
A[3, [4, 5]] = [1, 6]        # v4连接v5(1),v6(6)
A[4, 5] = 3                  # v5连接v6(3)
A = np.maximum(A, A.T)       # 保证对称性# 计算最短路径
G = nx.from_numpy_array(A)
d = nx.floyd_warshall_numpy(G)# 医院选址分析
max_distances = np.max(d, axis=0)
hospital = node[np.argmin(max_distances)]# 小学选址分析
weighted_dist = np.dot(d.T, students)
school = node[np.argmin(weighted_dist)]print(f"医院最佳选址: {hospital}")
print(f"小学最佳选址: {school}")