编程 BFS - 最短路径 - Python

Question

我是 Python 的新手，正在尝试将 BFS 写入 return 图形的最短路径。每条边的长度为6。

注意：这是 HackerRank 上的一个问题。

我的代码适用于 6 个测试用例中的 3 个，但其他 3 个失败。我不知道为什么，也无法真正调试，因为测试用例太大了。

我的代码是：

# Enter your code here. Read input from STDIN. Print output to STDOUT    

def shortestPath():
    testCases = int(raw_input())

    for a in range(testCases):
        nodes,edges = raw_input().strip().split(' ')
        numNodes,edges = [int(nodes), int(edges)]

        edgeList = []

        # input data
        for b in range(edges):
            a,b = raw_input().strip().split(' ')
            a,b = [int(a), int(b)]
            edgeList += [[a,b]]
        root = int(raw_input())

        marked = [] # what I've checked
        fringe = [root] # things to check
        distances = {} # what to return
        levels = {root: 0} # the level of each element
        counter = 1

        # do the BFS
        while fringe != []:
            node = fringe[0]
            fringe.remove(node)
            marked += [node]
            if counter > levels[node] + 1:
                counter = levels[node] + 1
            nbrsList = Nbrs(node, edgeList)
            for v in nbrsList:
                levels[v] = counter
                if v not in fringe and v not in marked:
                    distances[v] = 6*counter
                    fringe += [v]
            counter += 1

        listOfNodes = nodeList(edgeList, numNodes)

        for node in listOfNodes:
            if node != root:
                if node in distances:
                    print distances[node],
                else:
                    print -1,  
        print ""
    print ""

def nodeList(edges, numNodes):
    nodes = []
    for edge in edges:
        for element in edge:
            if element not in nodes:
                nodes += [element]
    nodes.sort()

    for x in range(1,numNodes+1):
        if x not in nodes:
            nodes += [x]
    nodes.sort()
    return nodes


def Nbrs(node, edges):
    tempList = []
    for edge in edges:
        if node in edge:
            for element in edge:
                if element != node:
                    tempList += [element]
    return tempList

比如我用的测试用例：

1
5 8
1 2
3 4
4 5
5 2
2 4
2 3
1 3
1 4
3

其中第一行是测试用例数，第二行是节点数，边数，剩下n-1行是边，最后一行是根。

这非常有效。我尝试将其更改为我能想到的所有内容，并且它似乎有效。然而，对于 70 个节点和 1988 个边的站点测试用例，我的答案对于许多节点来说太高了。

我们将不胜感激。

提前致谢，

Answer 1

编辑：原来的'problem'条件我确定是错误的，现在更正

您设置 counter 和 levels 的方式有问题。

假设R是根节点，A、B和C是其他节点，您的代码目前在

时有问题

R <-> A
A <-> B
R <-> B
B <-> C

并按此顺序评估关系。它认为从 R 到 C 的最短路径是 R -> A -> B -> C 而不是 R -> B -> C。

您可以通过重新排序您的示例输入集来重现该问题：

1
5 8
1 2
1 3 # Moved this and
1 4 # this up
3 4
4 5
5 2
2 4
2 3
3

这会更改您的输出，使 5 节点的距离变为 18 而不是 12。

我认为解决方案是将levels[v] = counter放在条件块中，即

for v in nbrsList:
    if v not in fringe and v not in marked:
        levels[v] = counter
        distances[v] = 6*counter
        fringe += [v]

编程 BFS - 最短路径 - Python

Programming a BFS - Shortest Path - in Python

python

graph

shortest-path

breadth-first-search