題組內容

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

(一)試寫出標籤設定法之步驟。（10 分）