min_dist = float('inf') best_site = None for i in range(GRID_SIZE): for j in range(GRID_SIZE): node = (i, j) dist = sum([dijkstra(node, (end[0], end[1]), graph)[1] for end in points]) if dist < min_dist: min_dist = dist best_site = (i, j) print(best_site) print(min_dist)优化该代码使得运行时间缩短

这段代码的时间复杂度是$O(n^3)$，其中 n 是 points 的长度。可以通过以下两种方式来优化代码：

1. 缓存已经计算过的距离，避免重复计算。可以使用一个字典来缓存距离，将距离作为键，最优点的坐标作为值。

2. 将计算距离的过程合并成一个函数，使用Numpy对数组进行向量化计算，以提高计算效率。

改进后的代码如下：

import numpy as np

GRID_SIZE = 10
points = [(2, 3), (5, 6), (8, 1)]

dist_cache = {}

def dijkstra_cache(start, end, graph):
    if (start, end) in dist_cache:
        return dist_cache[(start, end)]
    if (end, start) in dist_cache:
        return dist_cache[(end, start)]
    dist, path = dijkstra(start, end, graph)
    dist_cache[(start, end)] = (dist, path)
    return dist, path

def calc_dist(node):
    dist = sum([dijkstra_cache(node, (end[0], end[1]), graph)[0] for end in points])
    return dist

graph = np.zeros((GRID_SIZE, GRID_SIZE))
min_dist = float('inf')
best_site = None

for i in range(GRID_SIZE):
    for j in range(GRID_SIZE):
        node = (i, j)
        dist = calc_dist(node)
        if dist < min_dist:
            min_dist = dist
            best_site = node

print(best_site)
print(min_dist)

这样可以将时间复杂度降到 $O(n^2)$ 级别，计算速度会更快。