根据以下描述用python写出完整代码,并详细注释。问题描述: 对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,要求实现总体最优。 1、需求分析 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型(逻辑结构): 带权有向图 (权值计算: 距离频度) 核心算法: Floyd算法 输入数据(要求由用户输入): 各单位名称,距离,频度,单位个数。 输出数据: 所选单位名称。 运行环境:pycharm 2.概要设计: 如果超市是要选在某个单位,那么先用Floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个,那么就得到nn的一张表格,arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行),那么超市选在t单位处就是最优解。
时间: 2024-02-20 11:57:43 浏览: 21
以下是根据题目描述实现的完整代码,注释中有详细解释:
```python
# 定义一个带权有向图类
class WeightedDigraph:
def __init__(self, vertices):
self.vertices = vertices
self.num_vertices = len(vertices)
self.adj_matrix = [[0] * self.num_vertices for _ in range(self.num_vertices)]
def add_edge(self, start_vertex, end_vertex, weight):
start_idx = self.vertices.index(start_vertex)
end_idx = self.vertices.index(end_vertex)
self.adj_matrix[start_idx][end_idx] = weight
def floyd(self):
# 初始化路径矩阵和距离矩阵
dist = self.adj_matrix.copy()
path = [[None] * self.num_vertices for _ in range(self.num_vertices)]
for i in range(self.num_vertices):
for j in range(self.num_vertices):
if dist[i][j] != float('inf') and i != j:
path[i][j] = i
# Floyd算法核心代码
for k in range(self.num_vertices):
for i in range(self.num_vertices):
for j in range(self.num_vertices):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
path[i][j] = path[k][j]
return dist, path
# 从用户输入中获取各单位名称、距离和频度数据
num_units = int(input("请输入单位个数:"))
units = []
distances = {}
frequencies = {}
for i in range(num_units):
unit = input("请输入第{}个单位名称:".format(i+1))
distance = float(input("请输入{}到超市的距离:".format(unit)))
frequency = float(input("请输入{}单位人员到超市的频度:".format(unit)))
units.append(unit)
distances[unit] = distance
frequencies[unit] = frequency
# 构建带权有向图
graph = WeightedDigraph(units)
# 添加边及边权值
for start_vertex in units:
for end_vertex in units:
if start_vertex != end_vertex:
weight = distances[end_vertex] * frequencies[end_vertex]
graph.add_edge(start_vertex, end_vertex, weight)
# 调用Floyd算法求解最短路径
dist, path = graph.floyd()
# 找出总权值最小的单位
min_row_sum = float('inf')
min_row_idx = -1
for i in range(graph.num_vertices):
row_sum = sum(dist[i])
if row_sum < min_row_sum:
min_row_sum = row_sum
min_row_idx = i
optimal_unit = units[min_row_idx]
print("超市最优选址为:", optimal_unit)
```
与前面的代码相比,这份代码主要在输入数据的部分有所改动。在这里,我们通过`input()`函数从用户输入中获取各单位名称、距离和频度数据,并构建带权有向图来进行计算。其余部分与前面的代码基本相同。
需要注意的是,由于用户输入的数据可能存在错误,如空格、换行符等,因此在实际使用时需要对输入数据进行合理的格式化处理,以避免引入不必要的错误。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)