申論 1最短路徑問題（shortest path problem）為常用之數學模型。常用的求解演算法之一，為Dijkstra 所提出之標籤設定法（label setting algorithm）。該演算法在求解過程中將網路（network）之所有節點區分為永久節點（permanent node）及暫時節點（temporary node）兩類，再逐一設定永久節點之距離標籤（distance label）。任一節點成為永久節點之後，其距離標籤即不再變動。㈠試寫出標籤設定法之步驟。（10 分）㈡請設計一個具有下列性質之網路：含有不多於5 個節點及若干節線（arc）、含有長度為負值之節線、無負值長度之迴圈（negative cycle）、且以標籤設定法求解其最短路徑時將產生錯誤。請以圖形呈現所設計之網路，並使用標籤設定法求解最短路徑。請列舉詳細計算過程，並明確指出所產生之錯誤。請在圖形中明確標示各節線之長度及最短路徑起點。（15 分）