用Python编写BFS最短路径

Question

我是Python新手，正在尝试编写一个BFS来返回一个图的最短路径。每条边的长度是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

编辑：我确定的原始“问题”条件是错误的，现在更正

设置counter和levels时出现问题。在

假设R是根节点，A，B和{}是其他节点，那么当

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放在条件块中，即

^{pr2}$