用python语言实现的最短路spfa算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用python语言实现的最短路spfa算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2338字,纯文字阅读大概需要4分钟。
内容图文
![用python语言实现的最短路spfa算法](/upload/InfoBanner/zyjiaocheng/432/ad6ba534f5f64b2fbe0ef702af62e53e.jpg)
#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
后问题解除
内容总结
以上是互联网集市为您收集整理的用python语言实现的最短路spfa算法全部内容,希望文章能够帮你解决用python语言实现的最短路spfa算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。