[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])

说一说遇到的问题吧

 

1python列表的长度不固定，当需要读取固定位置的元素时要确定那个位置非空

2python不支持“++”，c++中“num[index++]”这种写法在这里行不通

3输入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)
    

 这是一个简单的向list中插入学生信息的程序。但是运行时候会发现，最后插入的值会覆盖前面的学生信息值

 

打印结果如下

请输入学生人数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

 后问题解除