python - 广度优先搜索 : shortest reach hackerrank

Question

给定一个由 N 个节点(标记为 1 到 N)组成的无向图，其中节点 S 表示起始位置，任意两个节点之间的边在图中的长度为 6 个单位。问题 here .

需要计算从起始位置(节点S)到图中所有其他节点的最短距离。

解决方案:这显然是最小距离的 floyd 算法的应用。

我试过的:我试过下面的代码，它通过了 2 个测试用例，但在所有其他测试用例中都失败了。对于偷偷摸摸的 bug ，我束手无策。我只想提示解决方案。就复杂性而言，最好提供其他方法的提示来解决此问题，但我正在寻找当前代码中的偷偷摸摸的错误。

def short_paths(cost, nodes):
for i in range(1, nodes):
  for j in range(1, nodes):
    for k in range(1, nodes):
      if cost[i][j] > cost[i][k]+cost[k][j]:
        cost[i][j] = cost[i][k]+cost[k][j]
return cost

tests = int(input())
while tests:
  x = input().split(" ")
  nodes, edges = int(x[0]), int(x[1])
  #initialize everything with infinity
  dp = [[1<<31 for i in range(nodes+1)] for i in range(nodes+1)]
  #distance between self is 0
  for i in range(nodes+1):
    dp[i][i] = 0
  while edges:
    p = input().split(" ")
    x, y = int(p[0]), int(p[1])
    #undirected graph
    dp[x][y] = 6
    dp[y][x] = 6
    edges -= 1
  src = int(input())
  dp = short_paths(dp, nodes+1)
  result = []
  for i in range(1, nodes+1):
    if src != i:
      if dp[src][i] == 1<<31:
        result.append("-1")
      else:
        result.append(dp[src][i])
  print(" ".join(str(e) for e in result))
  tests -= 1

Answer 1

我认为这几行有问题:

for i in range(1, nodes):
  for j in range(1, nodes):
    for k in range(1, nodes):

您应该首先迭代 k 以使结果正确:

尝试:

for k in range(1, nodes):
  for i in range(1, nodes):
    for j in range(1, nodes):

由于 DP 使用以前的结果，事实证明迭代的顺序对于获得正确的结果至关重要。

我记得顺序的方式是认为算法的第 k^th 次迭代仅使用从位置 1 到 k 的中间节点计算从 i 到 j 的最短路径。

但是，对于这个问题，这个 O(N^3) 方法会超时。更好的方法是从起始位置执行广度优先搜索，这将具有 N+M 的复杂度。