標籤修正演算法以Dequque實作
(Label-correcting algorithm-Dequeue implementation)
一、前言：
標籤修正法，Label correcting algorithm，求解最短路徑問題的演算法之一，屬於最短路徑問題中的單源最短路徑(Single Source Shortest Paths)，也就是給定起點，求出起點到各點的最短路徑。
本文以簡單介紹該演算法與以程式語言 C/C++ 來實踐出該演算法。
二、基本介紹：
此演算法求解任何網路(network)的最短路徑問題，即使網路中存在有長度(成本)為負值的節線，仍可以求解。但我仍需假設網路中沒有長度為負值的有向迴圈。
演算法如下圖所示：
此演算法是從沒有特定順序的走訪，只要任何一個節線(在演算法中以弧，arc(i,j) 表示 )，較缺乏效率。
故有人將其修正為以下的版本，稱之修正版本的標籤修正演算法Modified label correcting algorithm。在這個演算法可以發現在while中有一個節點清單LIST，這樣的修正讓演算法變得有效率，每次只要從LIST取出一節點，檢視該節點的節線，直到LIST為空而中止。
而本文主要要介紹的是Pape所提出的以Dequeue所實作的版本，為標籤演算法中效率最高者。此演算法的概念是以dequeue實踐上述的節點清單，來達成以特定規則將節點放入清單或從清單取出之目的。
Dequeue為Double-ended queue之意，是資料結構的一種，為有序集合，可以雙向增/刪佇列(queue)中的元素。
此演算法的獨到之處在於，如果一個節點曾經被檢視過，則由前端加入dequeue(push_front)，否則則由後段加入(push_back)；取出節點則一律由前端取出。此方法的想法在於先處理"舊"(已處理過)的節點，在處理"新"的節點，藉此提升演算法的效率。
三、實作
本階段會以C和C++實作，寫出兩版本的程式。
輸入檔案：network.txt
輸出檔案：shortestPath.txt
目的：以雙向佇列來實踐出修正版本的標籤修正法
(1)輸入檔案規格：
第一行 (節點數目) 空格 (節線數目)
第二行至第(節線數目+1)行 則為個個節線的基本資料，包含 起始節點、終止節點、節線長度(成本)。
在測試範例檔案中，節線長度必為整數，故稍後的程式與研究以integer的資料型態來處理。
(2)輸出檔案：
從起始節點(預設為0)從小到大排列，顯示到各點的最短距離與前置節點。
(3)程式碼：
四、比較與結論
如同前述，我們要比較是否因為依照特殊規定的加入/取出節點，而得到效率。因此我們稍加修改上述程式碼，將取出節點全部改為後端取出，再比較兩者在1.時間效率、2.while迴圈次數、3.各點被走訪次數 ，來知道效率的差異。
留言
張貼留言