Python Dijkstra算法

( 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