用python实现以下内容,提供代码。程序的主要功能(运用Floyd 算法) 2.1 输入功能 输入学校的单位总数; 输入学校各单位的名称; 输入学校各单位人员去超市频度; 输入学校各单位间的距离(用无向图的邻接矩阵表示) 2.2 求权值的功能 求出将超市设在各个单位时,所得总的权值,返回用数组存储。 2.3 求最优功能 从上述的各个权值中,选出最小值为最优,并将最优值和对应的选址储存在链表中,返回头指针。 2.4 显示功能 显示最优地址的地点、总权数以及各单位到它的距离。
时间: 2024-02-22 20:56:16 浏览: 63
以下是使用 Floyd 算法实现的代码:
```python
# 定义无穷大常量
INF = float("inf")
# 输入功能
def input_data():
n = int(input("请输入学校的单位总数:"))
names = []
freqs = []
for i in range(n):
name = input("请输入第{}个单位的名称:".format(i+1))
freq = int(input("请输入第{}个单位的人员去超市频度:".format(i+1)))
names.append(name)
freqs.append(freq)
matrix = []
for i in range(n):
row = input("请输入{}到其他单位的距离,用空格隔开:".format(names[i])).split()
row = [int(x) for x in row]
matrix.append(row)
return names, freqs, matrix
# Floyd算法求解最短路径
def floyd(matrix):
n = len(matrix)
for k in range(n):
for i in range(n):
for j in range(n):
if matrix[i][j] > matrix[i][k] + matrix[k][j]:
matrix[i][j] = matrix[i][k] + matrix[k][j]
# 求权值的功能
def calc_weights(freqs, matrix):
n = len(freqs)
weights = [0] * n
for i in range(n):
for j in range(n):
if i == j:
continue
weights[i] += freqs[j] * matrix[i][j]
return weights
# 求最优功能
def find_optimal(names, freqs, matrix):
n = len(freqs)
min_weight = INF
best_pos = -1
for i in range(n):
weights = calc_weights(freqs, matrix)
weight_sum = sum(weights)
if weight_sum < min_weight:
min_weight = weight_sum
best_pos = i
# 将超市移动到下一个单位
for j in range(n):
matrix[i][j] = matrix[j][i] = INF
result = {"pos": best_pos, "weight": min_weight, "distances": matrix[best_pos]}
return result
# 显示功能
def show_result(names, freqs, result):
pos = result["pos"]
weight = result["weight"]
distances = result["distances"]
print("最优地址为:{}".format(names[pos]))
print("总权数为:{}".format(weight))
print("各单位到最优地址的距离为:")
for i in range(len(names)):
print("{}:{}".format(names[i], distances[i]))
# 主程序
def main():
names, freqs, matrix = input_data()
floyd(matrix)
result = find_optimal(names, freqs, matrix)
show_result(names, freqs, result)
if __name__ == "__main__":
main()
```
运行程序后,按照提示输入数据即可得到最优地址和总权数以及各单位到最优地址的距离。
阅读全文