【原】単一ソース最短パス高速アルゴリズム(spfa)のpython 3.x実装

単一ソース最短パス高速アルゴリズム(spfa)のpython 3.x実装
0.一番前に書く
最近忙しいですね.書くことが少なくなりました.暇を見つけてこのドキュメントを書いて、粗末で噴き出さないでください~(後ろにアルゴリズムパッケージを作る準備をして、基礎のデータ構造とアルゴリズムを含んで、責任が重くて道が遠いと感じます)
1.SPFAのプロフィール[1]
SPFA(Shortest Path Faster Algorithm)アルゴリズムは、Bellman-fordのキュー最適化であり、非常に効率的な最短パスアルゴリズムである単一ソースの最短パスを求めるアルゴリズムである.多くの場合,与えられた図には負の重みエッジが存在し,Dijkstraのようなアルゴリズムは武力行使の余地がなく,Bellman‐Fordアルゴリズムの複雑さが高すぎてSPFAアルゴリズムが役に立つ.SPFAの複雑さは約O(kE)であり,kは各点の平均エンキュー回数である(一般的に,kは定数であり,疎図では2より小さい).しかし,SPFAアルゴリズムは安定性が劣り,稠密図ではSPFAアルゴリズムの時間的複雑さが劣化する.実装方法:キューを確立し、初期時にキューに開始点しかなく、テーブルを確立して開始点からすべての点までの最短パスを記録する(テーブルの初期値は極大値に割り当てられ、そのポイントから彼自身のパスは0に割り当てられる).その後、リラックス操作を実行し、キューにある点で開始点からすべての点への最短ルートをリフレッシュし、リフレッシュに成功し、リフレッシュされた点がキューにない場合は、その点をキューの最後に追加します.キューが空になるまで繰り返します.さらに、SPFAアルゴリズムは、図中に負の重みループがあるかどうか、すなわち、1ポイントのエンキュー回数がNを超えるかどうかを判断することもできる.
2.python実装[2]

"""
_spfa_simple    【xunalove】 csdn    
    http://blog.csdn.net/xunalove/article/details/70045815
_spfa_cut    【     】 cnblogs    
    http://www.cnblogs.com/hxsyl/p/3248391.html
"""
from queue import Queue
import numpy as np

npa = np.array
npm = np.mat


def spfa(s, node=0, inf=np.inf, method='simple'):
    """
          SPFA  ，Shortest Path Faster Algorithm
    :param s:    （      ）  s[i][j]  i j   
    :param node:  
    :param inf:    
    :param method:
    'simple':    ，      （       ）  
    :return:
    """
    if method == 'simple':
        return _spfa_simple(s, node, inf)
    elif method == 'cut':
        return _spfa_cut(s, node, inf)
    else:
        raise ValueError("method not found")


def _spfa_simple(s, node=0, inf=np.inf):
    """
            ，
            
    :param s:     （      ）  s[i][j]  i j   
    :param node:  
    :return:
    """
    a = npa(s)
    m, n = a.shape
    if m != n:
        raise ValueError("s      ")
    dis = np.ones(n) * inf
    vis = np.zeros(n, dtype=np.int8)
    dis[node] = 0
    vis[node] = 1
    que = Queue()
    prenode = -np.ones(n, dtype=np.int8)  #       ，    -1  
    que.put(node)
    while not que.empty():
        v = que.get()
        vis[v] = 0
        for i in range(n):
            temp = dis[v] + a[v][i]
            if a[v][i] > 0 and dis[i] > temp:
                dis[i] = temp  #      
                prenode[i] = v
                if vis[i] == 0:  #       i     ，  
                    que.put(i)
                    vis[i] = 1
    return dis, prenode


def _spfa_cut(s, node=0, inf=np.inf):
    """
            ，
           
    :param s:     （      ）  s[i][j]  i j   
    :param node:  
    :return:
    """
    a = npa(s)
    m, n = a.shape
    if m != n:
        raise ValueError("s      ")
    count = np.zeros(n, dtype=np.int8)
    dis = np.ones(n) * inf
    vis = np.zeros(n, dtype=np.int8)
    dis[node] = 0
    vis[node] = 1
    que = Queue()
    prenode = -np.ones(n, dtype=np.int8)  #       ，    -1  
    que.put(node)
    while not que.empty():
        v = que.get()
        vis[v] = 0
        for i in range(n):
            temp = dis[v] + a[v][i]
            if dis[i] > temp:
                dis[i] = temp  #      
                prenode[i] = v
                if vis[i] == 0:  #       i     ，  
                    count[i] += 1
                    if count[i] > n:
                        raise ValueError("       ")
                    que.put(i)
                    vis[i] = 1
    return dis, prenode

3.改善と説明

現在のコードは比較的粗末で、今後はより多くの補充が必要です.たとえば

は優先キュー最適化がないので、参考資料[4]を参照して

を最適化することができる.

試験用例を欠いて試験を行う

ディジェストラアルゴリズムとベルマンフロイドアルゴリズムとの比較

が欠けている.

アルゴリズムはさらに疎図に用いられ、時間効率が不安定である[4]

.
4.最後に書く
このコードをpypiにアップロードします.orgの時、404が間違っていることに気づき、メールボックスを検証していないと言った.pypiが海外にいるせいか、メールを検証するのに30分もかかった.吐き気がしない.
参考資料
[1]cnblogs SPFAアルゴリズムhttps://www.cnblogs.com/shadowland/p/5870640.html2018-3-5[2]コードクラウドオープンソースプロジェクトpython 3で実現したspfahttps://gitee.com/snowlandltd/snowland-algorithm-python/blob/master/SApy/graphtheory/spfa/_spfa.py2018-3-5[3]csdnが最も速く最も使いやすいspfaアルゴリズムhttp://blog.csdn.net/xunalove/article/details/700458152018-3-5【比較的おすすめ編、C++とPascalで実現】[4]cnblogs SPFAアルゴリズム学習ノートhttp://www.cnblogs.com/hxsyl/p/3248391.html2018-3-5【同様にこの編を推奨し、javaで実現し、優先キューで最適化する】