首页 > 编程语言 > 详细

Python Dijkstra算法

时间:2014-02-02 18:32:58      阅读:757      评论:0      收藏:0      [点我收藏+]
( VISIT_WHITE, VISIT_GRAY, VISIT_BLACK ) = ( 0, 1, 2 )
NO_ROAD = 1 << 31 

class CityNode:
    def __init__( self ):
        self.m_iDist = 1 << 31
        self.m_iParent = 0
        self.m_visit = VISIT_WHITE

def init( graph ):
    graph[0][1] = 15; graph[0][3] = 2; graph[0][4] = 12
    graph[1][2] = 6; graph[2][6] = 9; graph[3][2] = 8;
    graph[3][5] = 4; graph[4][6] = 3; graph[5][6] = 10
    graph[5][4] = 5; graph[6][1] = 4

def dijkstra( graph, start_pos ):
    city_num = len( graph )
    INF = 1 << 31
    city_arr = [ CityNode() for index in range( city_num ) ]
    count = 0
    city_arr[start_pos].m_iDist = 0
    while count < city_num:
        temp_min = INF
        next_pos = -1
        for index in range( city_num ):
            if temp_min > city_arr[index].m_iDist                and city_arr[index].m_visit != VISIT_BLACK:
                temp_min = city_arr[index].m_iDist
                next_pos = index
        city_arr[next_pos].m_visit = VISIT_BLACK
        for index in range( city_num ):
            if graph[next_pos][index] != NO_ROAD                and city_arr[index].m_visit != VISIT_BLACK                and city_arr[index].m_iDist > city_arr[next_pos].m_iDist + graph[next_pos][index]:
                city_arr[index].m_iDist = city_arr[next_pos].m_iDist + graph[next_pos][index]
                city_arr[index].m_visit = VISIT_GRAY
        count += 1
    for index in range( city_num ):
        print index, city_arr[index].m_iDist


if __name__ == ‘__main__‘:
    num = 7
    graph = [ [ NO_ROAD for col_index in range( num ) ]for raw_index in range( num ) ]
    init( graph )
    dijkstra( graph, 0 )

Python Dijkstra算法

原文:http://blog.csdn.net/pandora_madara/article/details/18894595

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!