申論題

一、最短路徑問題（shortest path problem）為常用之數學模型。常用的求解演 算法之一，為 Dijkstra 所提出之標籤設定法（label setting algorithm） 。該 演算法在求解過程中將網路（network）之所有節點區分為永久節點 （permanent node）及暫時節點（temporary node）兩類，再逐一設定永久 節點之距離標籤（distance label）。任一節點成為永久節點之後，其距離 標籤即不再變動。

(二)請設計一個具有下列性質之網路：含有不多於 5 個節點及若干節線 （arc）、含有長度為負值之節線、無負值長度之迴圈（negative cycle） 、 且以標籤設定法求解其最短路徑時將產生錯誤。請以圖形呈現所設計 之網路，並使用標籤設定法求解最短路徑。請列舉詳細計算過程，並 明確指出所產生之錯誤。請在圖形中明確標示各節線之長度及最短路 徑起點。（15 分）