我有一个数据集,这是一个大的未加权循环图.循环发生在约5-6路径的循环中.它由大约8000个节点组成,每个节点具有1-6个(通常约4-5个)连接.我正在进行单对最短路径计算,并已实现以下代码进行广度优先搜索.

from Queue import Queue

q = Queue()
parent = {}
fromNode = 'E1123'
toNode = 'A3455'

# path finding
q.put(fromNode)
parent[fromNode] = 'Root'

while not q.empty():
  # get the next node and add its neighbours to queue
  current = q.get()
  for i in getNeighbours(current):
    # note parent and only continue if not already visited
    if i[0] not in parent:
      parent[i[0]] = current
      q.put(i[0])

  # check if destination
  if current == toNode:
    print 'arrived at',toNode
    break

上面的代码使用了Python 2.6 Queue模块,getNeighbours()只是一个子程序,可以进行单个MysqL调用,并将邻居作为元组列表返回,例如： (( ‘富’,),( ‘巴’,)). sql调用很快.

代码工作正常但是测试到大约7层的深度需要大约20秒才能运行(2.5GHz Intel 4GB RAM OS X 10.6)

我欢迎任何关于如何改善此代码的运行时间的意见.