重庆理工大学学报(自然科学版)
重慶理工大學學報(自然科學版)
중경리공대학학보(자연과학판)
JOURNAL OF CHONGQING INSTITUTE OF TECHNOLOGY
2013年
7期
96-102,118
,共8页
复杂网络%近似算法%路标方法%最短路径问题
複雜網絡%近似算法%路標方法%最短路徑問題
복잡망락%근사산법%로표방법%최단로경문제
complex networks%approximation algorithm%landmark-based methods%shortestpath problem
针对大规模复杂网络中最短路径精确算法计算复杂的问题,提出一种基于路标的最短路径长度快速估计算法——SSPS算法.论证了SSPS算法的估计精度优于已有的Potamias算法;采用多种路标选择策略,使用多个数据集对比了SSPS算法与Potamias算法的性能.实验结果表明:SSPS算法的估计精度优于Potamias算法,且在最简单的随机路标选择策略中表现出良好的估计精度,可以较好地应用于大规模复杂网络最短路径长度的估算中.
針對大規模複雜網絡中最短路徑精確算法計算複雜的問題,提齣一種基于路標的最短路徑長度快速估計算法——SSPS算法.論證瞭SSPS算法的估計精度優于已有的Potamias算法;採用多種路標選擇策略,使用多箇數據集對比瞭SSPS算法與Potamias算法的性能.實驗結果錶明:SSPS算法的估計精度優于Potamias算法,且在最簡單的隨機路標選擇策略中錶現齣良好的估計精度,可以較好地應用于大規模複雜網絡最短路徑長度的估算中.
침대대규모복잡망락중최단로경정학산법계산복잡적문제,제출일충기우로표적최단로경장도쾌속고계산법——SSPS산법.론증료SSPS산법적고계정도우우이유적Potamias산법;채용다충로표선택책략,사용다개수거집대비료SSPS산법여Potamias산법적성능.실험결과표명:SSPS산법적고계정도우우Potamias산법,차재최간단적수궤로표선택책략중표현출량호적고계정도,가이교호지응용우대규모복잡망락최단로경장도적고산중.