python实现Dijkstra法

发布时间：2019-09-23 17:04:21编辑：auto阅读（1544）

1.图:







2.代码:




'''
file: py_Dijkstra.py

Dijkstra 最短路径算法
#本示例结果为:
S= [{'index': 1, 'val': 0}, {'index': 3, 'val': 15}, {'index': 2, 'val': 25}, {'index': 6, 'val': 30}, {'index': 5, 'val': 40}, {'index': 4, 'val': 50}]
dist= [0, 25, 15, 50, 40, 30]

'''
#############################################
debug=0
MAX_NUM=10000
v_num=6
#S 放 最短路径结点添加过程
S=[]#[{'index': 1, 'val': 0},...]
#dist放各个步骤临时dist值
dist=[]
edge=[
    [0,30,15,MAX_NUM,MAX_NUM,MAX_NUM],
    [5,0,MAX_NUM,MAX_NUM,20,30],
    [MAX_NUM,10,0,MAX_NUM,MAX_NUM,15],
    [MAX_NUM,MAX_NUM,MAX_NUM,0,MAX_NUM,MAX_NUM],
    [MAX_NUM,MAX_NUM,MAX_NUM,10,0,MAX_NUM],
    [MAX_NUM,MAX_NUM,MAX_NUM,30,10,0]
]
#############################################
def init(start):
    if(debug):
        print("[init]")
    S.append({'index':start,'val':0})
    i=0
    while(i<v_num):
        dist.append(edge[start-1][i])
        i=i+1

######################
def v_in_S(v):
    i=0
    while(i<len(S)):
        if(v==S[i]['index']):
            return "YES"
        i=i+1
    
    return "NO"

######################
def get_min():
    if(debug):
        print("[get_min]")
    if(len(dist)<1):
        return {'index':-1,'val':0}#这里该直接exit(1)的,这里返回值，是方便调试而已
    i=0
    min_val=MAX_NUM
    min_index=0
    while(i<len(dist)):
        if(v_in_S(i+1)=="NO"):
            if(dist[i] < MAX_NUM and dist[i] > 0 and min_val>dist[i]):
                min_val=dist[i]
                min_index=i
        i=i+1
    return {'index':min_index+1,'val':min_val}


######################
def update_dist():
    tmp_index=S[len(S)-1]['index']
    tmp_val=S[len(S)-1]['val']
    if(debug):
        print("[update_dist]","tmp_index=",tmp_index,";tmp_val=",tmp_val)    
    i=0
    while(i<v_num):
        if(v_in_S(i+1)=="NO"):
            i_dist=tmp_val+edge[tmp_index-1][i]
            if(debug):
                print("i=",i,";i_dist=",i_dist)
            if(dist[i]>i_dist):
                dist[i]=i_dist
        i=i+1
    if(debug):
        print("after update dist:dist=",dist)
    
######################
def process():
    if(debug):    
        print("[process]")
    i=0
    S_len=len(S)
    while(v_num != S_len and i<v_num):
        min_vertex=get_min()
        if(debug):
            print("i=",i,";min_vertex=",min_vertex)        
            print("len(S)=",len(S),";S=",S)
        if(min_vertex['index']>0):
            if(debug):
                print("----BEFORE append:   len(S)=",len(S),";S=",S)
            S.append(min_vertex)
            if(debug):
                print("====AFTER append:   len(S)=",len(S),";S=",S)            
            update_dist()
            
        i=i+1
        S_len=len(S)

######################
def py_Dijkstra(start):
    init(start)
    print("初始条件:\n","\tstart=",start,"\n\tS=",S,"\n\tdist=",dist)
    process()
    print("结果:\n","\tS=",S,"\n\tdist=",dist)
    
#############################################
if(__name__=="__main__"):
    py_Dijkstra(1)








3.结果:

初始条件:
 	start= 1 
	S= [{'index': 1, 'val': 0}] 
	dist= [0, 30, 15, 10000, 10000, 10000]
结果:
 	S= [{'index': 1, 'val': 0}, {'index': 3, 'val': 15}, {'index': 2, 'val': 25}, {'index': 6, 'val': 30}, {'index': 5, 'val': 40}, {'index': 4, 'val': 50}] 
	dist= [0, 25, 15, 50, 40, 30]

关键字：