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 のリストは固定されていません。固定位置の要素を読み取る必要がある場合は、その位置が空でないことを確認する必要があります

2Python は「++」と「num[index++]」の記述方法をサポートしていません。 C++ の " はここでは機能しません

3 int 型の値の入力は最初に入力する必要があります。次に int() を使用して変換を強制します

4 グローバル変数は global で宣言する必要があり、また、グローバル変数もグローバルで宣言する必要がありますfunction

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 を

Python コード

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

に変更すると、問題は解決されます