[python]python言語で実現される最短spfaアルゴリズム

最近pythonを勉強していますが、cシリーズの言語中毒者にとって多くの問題は古い認識を捨てて再理解する必要があります.
 

#coding=utf-8
global n, m, k, edge, head, dis, stack, vis, nMax, mMax, inf
nMax = 100
mMax = 10000
inf = 1e+10
class e(object):
    pass
n = 0
k = 0
m = 0
eg = e()
edge = []
head = [0]
dis = [0]
stack = [0]
vis = [0]

def addedge(a, b, c):
    global k, edge, head
    ed = e()
    ed.u = a #you can delect it
    ed.v = b
    ed.w = c
    ed.next = head[a]
    edge.append(ed)
    head[a]=k
    k+=1
    pass

def spfa():
    global n, m, k, edge, head, dis, stack, vis,inf
    i = top = 0
    for i in range(0 , n):
        dis[i] = inf
        vis[i] = 0
    dis[0] = 0
    vis[0] = 1
    top+=1
    stack[top] = 0
    while(top!=0):
        u = stack[top]
        top-=1
        i = head[u]
        while(i!=0):
            v = edge[i].v
            if dis[v] > dis[u]+edge[i].w:
                dis[v] = dis[u]+edge[i].w
                if(vis[v]==0):
                    vis[v] = 1
                    top+=1
                    stack[top] = v
            i = edge[i].next
        vis[u] = 0
    pass
  
if __name__ == '__main__':
    u = v = l = i = 0
    for i in range(0,nMax):
        head.append(0);
        dis.append(0)
        vis.append(0)
        stack.append(0)
    while(1):
        na = input()
        n = int(na)
        ma = input()
        m = int(ma)
        edge=[0]
        k = 1
        for i in range(0,n):
            head[i] = 0
        for i in range(0,m):
            ua = input()       
            va = input()
            la = input()
            u = int(ua)
            v = int(va)
            l = int(la)
            addedge(u,v,l)
        spfa()  
        for i in range(1,n):
            print(dis[i])

問題を話しましょう
 
1 pythonリストの長さは固定されていません.固定位置の要素を読み込む必要がある場合は、その位置が空でないことを確認します.
2 pythonは「++」をサポートしていません.c++の「num[index+]」という書き方はここでは通用しません.
3 intタイプの値を入力するには、まずint()をinputしてからint()を強制的に変換する必要があります.
4グローバル変数はglobalで宣言し、関数でもglobalで宣言します.
5非常に邪悪なことを言う
 

'''
Created on 2014 7 5 

@author: bbezxcy
'''
global stu,k
class student:
    pass

stu = []

def addStudent1(nm ,ag):
    global stu,k
    stu[k].name = nm
    stu[k].age = ag
    k+=1
    pass

def addStudent(nm ,ag):
    global stu,k
    stu[k].name = nm
    stu[k].age = ag
    k+=1
    pass
if __name__ == '__main__':
    num = 0
    k = 0
    strn = input("       ")
    num = int(strn)
    ss = student()
    for i in range(0 ,num):
        stu.append(ss)
    for i in range(0 ,num):
        nm = input()
        ag = input()
        addStudent(nm ,ag)
    for i in range(0,num):
        print(stu[i].name)
        print(stu[i].age)
    

これはリストに学生情報を簡単に挿入するプログラムです.ただし、実行時には、最後に挿入した値が前の学生情報値を上書きすることがわかります.
 
印刷結果は次のとおりです.

       3
zys
20
xcy
19
ghz
20

    
ghz
20
ghz
20
ghz
20

addstudentを

def addStudent(nm ,ag):
    global stu,k
    s = student()
    s.name = nm
    s.age = ag
    stu.append(s)
    k+=1
    pass

後問題解除