计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2011年
5期
274-277
,共4页
地理信息系统%路径分析%最短路径%Dijsktra算法%文件缓冲
地理信息繫統%路徑分析%最短路徑%Dijsktra算法%文件緩遲
지리신식계통%로경분석%최단로경%Dijsktra산법%문건완충
针对传统Dijsktra算法运算需耗费大量的内存空间和运算时间,难以满足GIS这种大数据量的路径选择要求,提出一种改进的Dijsktra算法.该算法采用利于实现的结点-关联弧段优化存储结构,从传统算法的临时结点中,将大量与永久结点不直接连通的点划分为未标记结点,很大程度上减少了临时结点的数量,提高了算法的搜索效率,同时,运算时通过拓扑索引和临时文件缓冲,大大节省了内存空间,使得算法的空间复杂度为O(n).试验和实际应用结果证明了算法的有效性.
針對傳統Dijsktra算法運算需耗費大量的內存空間和運算時間,難以滿足GIS這種大數據量的路徑選擇要求,提齣一種改進的Dijsktra算法.該算法採用利于實現的結點-關聯弧段優化存儲結構,從傳統算法的臨時結點中,將大量與永久結點不直接連通的點劃分為未標記結點,很大程度上減少瞭臨時結點的數量,提高瞭算法的搜索效率,同時,運算時通過拓撲索引和臨時文件緩遲,大大節省瞭內存空間,使得算法的空間複雜度為O(n).試驗和實際應用結果證明瞭算法的有效性.
침대전통Dijsktra산법운산수모비대량적내존공간화운산시간,난이만족GIS저충대수거량적로경선택요구,제출일충개진적Dijsktra산법.해산법채용리우실현적결점-관련호단우화존저결구,종전통산법적림시결점중,장대량여영구결점불직접련통적점화분위미표기결점,흔대정도상감소료림시결점적수량,제고료산법적수색효솔,동시,운산시통과탁복색인화림시문건완충,대대절성료내존공간,사득산법적공간복잡도위O(n).시험화실제응용결과증명료산법적유효성.
