给出python代码:对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,要求实现总体最优。 1、需求分析 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型(逻辑结构): 带权无向图 (权值计算: 距离频度) 核心算法: Floyd算法 输入数据( n = int(input('请输入图中顶点个数:')) e = int(input('请输入图中边的条数:')) t = Graph(n, e) print('学校超市最佳选址*') print() print('请输入存在路径的两个单位以及相通两个单位间的距离(用空格隔开)') print()): 各单位名称,各单位之间的距离,去超市的频度,单位个数。 输出数据: 所选单位名称。 运行环境:pycharm 2.概要设计: 如果超市是要选在某个单位,那么先用Floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个,那么就得到nn的一张表格,arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行),那么超市选在t单位处就是最优解。
时间: 2024-02-20 14:02:37 浏览: 20
好的,根据您的要求,我为您编写了如下代码:
```
class Graph:
def __init__(self, n, e):
self.n = n
self.e = e
self.arc = [[float('inf')]*n for _ in range(n)]
self.freq = [0]*n
self.name = ['']*n
def add_edge(self, v1, v2, weight):
self.arc[v1][v2] = weight
self.arc[v2][v1] = weight
def set_freq(self, v, freq):
self.freq[v] = freq
def set_name(self, v, name):
self.name[v] = name
def floyd(graph):
n = graph.n
arc = graph.arc
for k in range(n):
for i in range(n):
for j in range(n):
if arc[i][j] > arc[i][k] + arc[k][j]:
arc[i][j] = arc[i][k] + arc[k][j]
return arc
n = int(input('请输入图中顶点个数:'))
e = int(input('请输入图中边的条数:'))
t = Graph(n, e)
for i in range(n):
name = input('请输入第%d个单位的名称:' % (i+1))
t.set_name(i, name)
freq = int(input('请输入第%d个单位的去超市的频度:' % (i+1)))
t.set_freq(i, freq)
for i in range(e):
v1, v2, weight = input('请输入存在路径的两个单位以及相通两个单位间的距离(用空格隔开):').split()
v1, v2, weight = int(v1), int(v2), int(weight)
t.add_edge(v1, v2, weight*t.freq[v2])
arc = floyd(t)
min_row = float('inf')
min_row_index = 0
for i in range(n):
row_sum = sum(arc[i])
if row_sum < min_row:
min_row = row_sum
min_row_index = i
print('学校超市最佳选址是:', t.name[min_row_index])
```
在代码中,我们首先定义了一个Graph类,用于存储图的相关信息。在输入数据时,我们分别输入各单位名称、各单位去超市的频度以及各单位间的距离,然后根据这些信息建立一个带权无向图。然后,我们使用floyd算法来求出所有顶点之间的最短距离/最小权值,得到一个n*n的表格,然后找到表格中和最小的那一行,即可确定超市的最佳选址。最后,输出所选单位的名称。
希望这个代码可以帮到您。如果您有任何问题,请随时提出。