[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 = inf
vis = 0
dis[0] = 0
vis[0] = 1
top+=1
stack[top] = 0
while(top!=0):
u = stack[top]
top-=1
i = head
while(i!=0):
v = edge.v
if dis[v] > dis+edge.w:
dis[v] = dis+edge.w
if(vis[v]==0):
vis[v] = 1
top+=1
stack[top] = v
i = edge.next
vis = 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 = 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)
　　说一说遇到的问题吧
　　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.name)
print(stu.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
　　后问题解除