The shortest path spfa algorithm implemented in python language

巴扎黑
Release: 2016-12-07 11:31:18
Original
3191 people have browsed it

I am learning python recently. For a person who is deeply addicted to the C series language, there are many problems that need to be abandoned and re-understood

#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])
Copy after login

Let’s talk about the problems encountered

1The length of the python list is not fixed. When you need to read an element at a fixed position, you must make sure that the position is not empty

2Python does not support "++", and the writing method of "num[index++]" in C++ does not work here

3Inputting int type values ​​​​should be entered first Then use int() to force conversion

4 Global variables must be declared with global, and they must also be declared with global in the function

5 Let’s talk about a very weird thing

'''
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)
Copy after login

This is a simple way to insert student information into the list program. But when running, you will find that the last inserted value will overwrite the previous student information value

The printed result is as follows

请输入学生人数3
zys
20
xcy
19
ghz
20
输出结果
ghz
20
ghz
20
ghz
20
Copy after login

After changing addstudent to

Python code

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

the problem is solved


Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template