dijkstra_4.py 文件源码

python
阅读 18 收藏 0 点赞 0 评论 0

项目:siren 作者: ozsolarwind 项目源码 文件源码
def dijkstra(aGraph, start):
   #  print '''Dijkstra's shortest path'''
     # Set the distance for the start node to zero
    start.set_distance(0)

     # Put tuple pair into the priority queue
    unvisited_queue = [(v.get_distance(), v) for v in aGraph]
    heapq.heapify(unvisited_queue)

    while len(unvisited_queue):
         # Pops a vertex with the smallest distance
        uv = heapq.heappop(unvisited_queue)
        current = uv[1]
        current.set_visited()

        for next in current.adjacent:
             # if visited, skip
            if next.visited:
                continue
            new_dist = current.get_distance() + current.get_weight(next)

            if new_dist < next.get_distance():
                next.set_distance(new_dist)
                next.set_previous(current)
#                print 'updated : current = %s next = %s new_dist = %s' \
#                        %(current.get_id(), next.get_id(), str(next.get_distance()))
#            else:
#                print 'not updated : current = %s next = %s new_dist = %s' \
#                        %(current.get_id(), next.get_id(), str(next.get_distance()))

         # Rebuild heap
         # 1. Pop every item
        while len(unvisited_queue):
            heapq.heappop(unvisited_queue)
         # 2. Put all vertices not visited into the queue
        unvisited_queue = [(v.get_distance(), v) for v in aGraph if not v.visited]
        heapq.heapify(unvisited_queue)
    return
评论列表
文章目录


问题


面经


文章

微信
公众号

扫码关注公众号