贡献python prim多源最短路搜索算法 numba加速方法的demo和总结

1、测试两个算法

#coding:utf-8

import time

import numba

import numpy as np

'''

使用numba加速总结，

(1)、在数值计算比如int float double等类型计算时

使用numba进行加速，速度可加快，string类型数据不能使用numba进行加速。

（2）、在数值计算时：小循环别使用numba，循环大于100以上可使用numba加速。

（3）、在小循环的时候切换进程发费时间，所以速度慢。

（4）、在循环计算小于等于1秒之内的计算时间，别使用numba加速，大于1秒的计算时间可使用。

'''

@numba.jit

def test1(ls):

    n = len(ls)

    dt = np.zeros((n,n))

    for i,item in enumerate(ls):

        for j,val in enumerate(ls):

            dt[i,j]=(val+item)

    return dt

@numba.njit

def prim(G,start=0):

    N = len(G)

    k = start

    MST = []

    vis = np.zeros(N)

    vis[0] = 1

    while k < N-1:

        minw = np.inf

        u,v=0,0

        for i in range(N):

            for j in range(N):

                if vis[i] ==1 and vis[j] == 0:

                    if G[i,j] < minw:

                        minw = G[i,j]

                        u,v=i,j

        vis[v] = 1

        k = k+1

        MST.append([u,v,minw].copy())

    return MST

if __name__=="__main__":

    ls = list(float(i) for i in range(30000))

    n=500

    G = np.random.randint(100,1000,(n,n))

    st = time.time()

    # re = test1(ls)

    re1 = prim(G)

    print(re1[-10:])

    print(time.time()-st)