根据以下描述用python写出完整代码,并详细注释。问题描述: 对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,要求实现总体最优。 1、需求分析 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型(逻辑结构): 带权有向图 (权值计算: 距离频度) 核心算法: Floyd算法 输入数据(要求由用户输入): 各单位名称,各单位之间是否联通,去超市的频度,单位个数。 输出数据: 所选单位名称。 运行环境:pycharm 2.概要设计: 如果超市是要选在某个单位,那么先用Floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个,那么就得到nn的一张表格,arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行),那么超市选在t单位处就是最优解。
时间: 2024-02-20 21:57:56 浏览: 70
以下是完整代码和详细注释,根据您的要求,输入数据由用户手动输入:
```python
# 导入numpy库,用于实现矩阵计算
import numpy as np
# 输入单位名称和去超市的频度
names = []
frequencies = []
n = int(input("请输入单位个数: "))
for i in range(n):
name = input("请输入第{}个单位名称: ".format(i+1))
frequency = int(input("请输入{}单位去超市的频度: ".format(name)))
names.append(name)
frequencies.append(frequency)
# 输入各单位之间是否联通,构建邻接矩阵,0表示不联通,inf表示自己到自己的距离为无穷大
adj_matrix = []
for i in range(n):
row = []
for j in range(n):
if i == j:
row.append(float('inf'))
else:
connected = input("请问{}单位是否和{}单位联通?(是/否)".format(names[i], names[j]))
if connected == '是':
distance = int(input("请输入{}单位和{}单位之间的距离: ".format(names[i], names[j])))
weight = distance * frequencies[j]
row.append(weight)
else:
row.append(float('inf'))
adj_matrix.append(row)
# 使用Floyd算法计算各顶点间最短路径/最小权值
for k in range(n):
for i in range(n):
for j in range(n):
adj_matrix[i][j] = min(adj_matrix[i][j], adj_matrix[i][k] + adj_matrix[k][j])
# 找出和最小的那一行
min_row = np.argmin(np.sum(adj_matrix, axis=1))
# 输出所选单位名称
print("超市应选在{}单位处".format(names[min_row]))
```
使用方法:将以上代码复制到pycharm中运行即可。根据提示输入各个单位的信息,最后输出超市应选在哪个单位处。
阅读全文