動態最短路徑問題之研究

Abstract

本文在解決動態最短路徑問題。於一個有ｎ個預點且各邊長度相同之圖形Ｇ上，我們 要做一序列的兩類動作：一是報告任意兩頂點間之最短路徑；一是於圖形Ｇ上加入一 個邊。隨著一個個邊的加入，頂點間之最短路徑亦跟著變動。本文提出之方法，利用 特別的資料結構來表示圖形，可以在Ｏ（Ｋ）之時間內報告兩頂點間之最短路徑，其 中ｋ＝＜ｎ，是所報告之路徑的邊數；並可在ｏ（ｎ3 ｌｎｎ）之時間內完成一序列 包含至多ｏ（ｎ2 ）個加入邊的動作。再者，本文之方法亦可解決於具任意邊長之圖 形上之同類問題，且實際費時將低於前人提出之方法。