用python语言实现的最短路spfa算法
程序员文章站
2022-04-04 19:44:49
...
最近在学习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改为
Python代码
def addStudent(nm ,ag): global stu,k s = student() s.name = nm s.age = ag stu.append(s) k+=1 pass
后问题解除