计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2012年
13期
251-253
,共3页
沈海澜%王玉斌%陈再良%曹子文
瀋海瀾%王玉斌%陳再良%曹子文
침해란%왕옥빈%진재량%조자문
最短路径%SPFA算法%分层图%同步循环%队列%数据结构
最短路徑%SPFA算法%分層圖%同步循環%隊列%數據結構
최단로경%SPFA산법%분층도%동보순배%대렬%수거결구
针对数据结构课程教学中顶点数受限的最短路径问题,提出一种基于图分层的改进SPFA算法——K_SPFA.借鉴图分层思想,将原图拓展为层数与顶点限制数相等的图层,将原图中的边拓展成图层间的边.利用2个同步循环的FIFO队列和贪心策略,对SPFA算法的数据存储结构和最短路径更新操作进行改进,从而实现原图中顶点数受限的最短路径寻找.实验结果表明,K_SPFA具有较低的平均时间复杂度.
針對數據結構課程教學中頂點數受限的最短路徑問題,提齣一種基于圖分層的改進SPFA算法——K_SPFA.藉鑒圖分層思想,將原圖拓展為層數與頂點限製數相等的圖層,將原圖中的邊拓展成圖層間的邊.利用2箇同步循環的FIFO隊列和貪心策略,對SPFA算法的數據存儲結構和最短路徑更新操作進行改進,從而實現原圖中頂點數受限的最短路徑尋找.實驗結果錶明,K_SPFA具有較低的平均時間複雜度.
침대수거결구과정교학중정점수수한적최단로경문제,제출일충기우도분층적개진SPFA산법——K_SPFA.차감도분층사상,장원도탁전위층수여정점한제수상등적도층,장원도중적변탁전성도층간적변.이용2개동보순배적FIFO대렬화탐심책략,대SPFA산법적수거존저결구화최단로경경신조작진행개진,종이실현원도중정점수수한적최단로경심조.실험결과표명,K_SPFA구유교저적평균시간복잡도.
