计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
6期
180-184,213
,共6页
组合算法%单源最短路径%SPFA算法%Bellman-Ford算法
組閤算法%單源最短路徑%SPFA算法%Bellman-Ford算法
조합산법%단원최단로경%SPFA산법%Bellman-Ford산법
Combinational algorithm%Single-source shortest paths%SPFA algorithm%Bellman-Ford algorithm
SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法.该算法实现简单,实际运行效果较好,在国内有着比较大的影响力.但遗憾的是,该算法一直缺少正确的理论分析.对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为(O)(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去.对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕.最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较.
SPFA(Shortest Path Faster Algorithm)算法是一種對任意有嚮圖求單源最短路徑的算法.該算法實現簡單,實際運行效果較好,在國內有著比較大的影響力.但遺憾的是,該算法一直缺少正確的理論分析.對該算法進行瞭分析,指齣該算法在不存在源點可達負圈的有嚮圖中,最壞情況運行時間為(O)(|V||E|);在存在源點可達負圈的有嚮圖中,算法將無限運行下去.對此,給齣瞭改進的SPFA算法,對于任意的有嚮圖,該算法能夠在O(|V||E|)內運行完畢.最後,從實際運行角度將SPFA算法與其它思想上同源的最短路徑算法進行瞭一繫列比較.
SPFA(Shortest Path Faster Algorithm)산법시일충대임의유향도구단원최단로경적산법.해산법실현간단,실제운행효과교호,재국내유착비교대적영향력.단유감적시,해산법일직결소정학적이론분석.대해산법진행료분석,지출해산법재불존재원점가체부권적유향도중,최배정황운행시간위(O)(|V||E|);재존재원점가체부권적유향도중,산법장무한운행하거.대차,급출료개진적SPFA산법,대우임의적유향도,해산법능구재O(|V||E|)내운행완필.최후,종실제운행각도장SPFA산법여기타사상상동원적최단로경산법진행료일계렬비교.
