標題: | 動態最短路徑問題之研究 |
作者: | 林志忠 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 |
顯示於類別: | 畢業論文 |