標題: 動態最短路徑問題之研究
作者: 林志忠
LIN, ZHI-ZHONG
張瑞川
ZHANG, RUI-SHUAN
資訊科學與工程研究所
關鍵字: 動態最短路徑;資料結構;圖形;DATA-STRUCTURE;O(K);GRAPHIC-IMAGE
公開日期: 1988
摘要: 本文在解決動態最短路徑問題。於一個有n個預點且各邊長度相同之圖形G上,我們 要做一序列的兩類動作:一是報告任意兩頂點間之最短路徑;一是於圖形G上加入一 個邊。隨著一個個邊的加入,頂點間之最短路徑亦跟著變動。本文提出之方法,利用 特別的資料結構來表示圖形,可以在O(K)之時間內報告兩頂點間之最短路徑,其 中k=<n,是所報告之路徑的邊數;並可在o(n3 lnn)之時間內完成一序列 包含至多o(n2 )個加入邊的動作。再者,本文之方法亦可解決於具任意邊長之圖 形上之同類問題,且實際費時將低於前人提出之方法。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772394077
http://hdl.handle.net/11536/53833
顯示於類別:畢業論文