ホームページ > バックエンド開発 > Python チュートリアル > Python言語で実装された最短パスSPFAアルゴリズム

Python言語で実装された最短パスSPFAアルゴリズム

巴扎黑
リリース: 2016-12-07 11:31:18
オリジナル
3222 人が閲覧しました

私は最近 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
ログイン後にコピー

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


関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート