用python语言实现的最短路spfa算法

最近在学习python，对于一个c系列语言深度中毒的人来说很多问题需要抛弃旧的认识并重新理解

#coding=utf-8global n, m, k, edge, head, dis, stack, vis, nMax, mMax, infnMax = 100mMax = 10000inf = 1e+10<mark>来源gaodaimacom搞#^代%!码网</mark>class e(object):    passn = 0k = 0m = 0eg = 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    passdef 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,kclass student:    passstu = []def addStudent1(nm ,ag):    global stu,k    stu[k].name = nm    stu[k].age = ag    k+=1    passdef addStudent(nm ,ag):    global stu,k    stu[k].name = nm    stu[k].age = ag    k+=1    passif __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中插入学生信息的程序。但是运行时候会发现，最后插入的值会覆盖前面的学生信息值

打印结果如下

请输入学生人数3zys20xcy19ghz20输出结果ghz20ghz20ghz20

把addstudent改为

Python代码

def addStudent(nm ,ag):      global stu,k      s = student()      s.name = nm      s.age = ag      stu.append(s)      k+=1      pass

后问题解除

喜欢 (0)赏

[搞代码]

分享 (0)