用python实现以下内容,提供代码。程序的主要功能(运用Floyd 算法) 1. 输入功能 : 输入学校的单位总数;输入图的边数; 输入学校各单位的名称; 输入学校各单位人员去超市频度; 输入存在边的两个单位的名称(用空格隔开);相通两个单位间的距离(可为浮点数) 2. 求权值的功能 : 求出将超市设在各个单位时,所得总的权值,返回用数组存储。 3. 求最优功能 : 从上述的各个权值中,选出最小值为最优,并将最优值和对应的选址储存在链表中,返回头指针。 4. 显示功能 : 显示最优地址的地点、总权数以及各单位到它的距离。
时间: 2024-02-22 14:57:04 浏览: 112
以下是使用 Python 实现 Floyd 算法的程序,实现输入学校的单位总数、图的边数、各单位的名称、各单位人员去超市频度、存在边的两个单位的名称以及相通两个单位间的距离等功能。其中,我们将单位名称和距离存储在字典中,并使用三维数组存储各个单位之间的最短距离。
```python
import sys
INF = float('inf')
# 输入学校的单位总数,图的边数,各单位的名称以及各单位人员去超市频度
n = int(input("请输入学校的单位总数:"))
m = int(input("请输入图的边数:"))
name = [input("请输入第 %d 个单位的名称:" % (i + 1)) for i in range(n)]
frequency = [int(input("请输入 %s 的人员去超市频度:" % name[i])) for i in range(n)]
# 初始化距离矩阵
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
# 输入存在边的两个单位的名称以及相通两个单位间的距离
for i in range(m):
u, v, w = input("请输入存在边的两个单位的名称(用空格隔开)及它们之间的距离:" ).split()
u, v, w = name.index(u), name.index(v), float(w)
dist[u][v] = w
dist[v][u] = w
# Floyd 算法求最短距离
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 求出将超市设在各个单位时,所得总的权值
value = [0] * n
for i in range(n):
for j in range(n):
value[i] += frequency[j] * dist[i][j]
# 选出最小值为最优,并将最优值和对应的选址储存在链表中
best_value, best_pos = min((value[i], i) for i in range(n))
result = [(name[best_pos], best_value)]
for i in range(n):
if i != best_pos and value[i] == best_value:
result.append((name[i], best_value))
# 显示最优地址的地点、总权数以及各单位到它的距离
print("最优地址的地点是:", result[0][0])
print("总权数是:", result[0][1])
print("各单位到 %s 的距离是:" % result[0][0])
for i in range(n):
print("%s:%.2f" % (name[i], dist[i][best_pos]))
```
注意:本程序只实现了输入、求权值、求最优和显示等功能,实现了 Floyd 算法的核心部分。如果要完整实现该题目,还需要增加一些异常处理、输入格式验证和用户交互等功能。
阅读全文