广度优先搜索：最短距离 hackerrank

Question

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

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

解法：这显然是最小距离的floyd算法的应用。

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

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 的复杂度。

Answer 2

import queue 

def BFS(s):
    q = queue.Queue()
    q.put(s)
    visited[s] = True
    dist[s] = 0

    while not q.empty():
        u = q.get()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                q.put(v)
                dist[v] = dist[u] + 1

Q = int(input())
for _ in range(Q):
    n, m = map(int, input().split())

    graph = [[] for i in range(n)]
    visited = [False for i in range(n)]
    dist = [-1 for i in range(n)]

    for i in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        graph[u].append(v)
        graph[v].append(u)
    s = int(input()) - 1

    BFS(s)
    for i in range(n):
        if i == s:
            continue
        print(dist[i]*6 if dist[i] != -1 else '-1', end = ' ')
    print()

只需使用普通 BFS

广度优先搜索：最短距离 hackerrank

Breadth first search: shortest reach hackerrank

python

algorithm

shortest-path

floyd-warshall