標籤修正演算法以Dequque實作(Label-correcting algorithm-Dequeue implementation)

標籤修正演算法以Dequque實作
(Label-correcting algorithm-Dequeue implementation)

一、前言：

標籤修正法，Label correcting algorithm，求解最短路徑問題的演算法之一，屬於最短路徑問題中的單源最短路徑(Single Source Shortest Paths)，也就是給定起點，求出起點到各點的最短路徑。

本文以簡單介紹該演算法與以程式語言 C/C++ 來實踐出該演算法。

補充：詳細的演算法介紹與分類，可以參考台灣最詳盡的演算法網站-演算法筆記去學習。(連結：http://www.csie.ntnu.edu.tw/~u91029/Path.html)

二、基本介紹：

此演算法求解任何網路(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)程式碼：

	#include <stdio.h>//Standard input & output
	#include <deque>//for LIST(STL container :deque)
	#include <vector>//for implement adjList(STL container)
	#include <list>//for implement adjList(STL container)
	#include <iostream>
	#include <iomanip>
	#include <windows.h>//get freq & cycle
	using namespace std;
	FILE *finput;//The file pointer to read file
	FILE *foutput;//The file pointer for writing the result
	int main(void){
	//variable declaration
	int i,j;//the for-loop counter
	int round;//calculate while-loop
	int vertices, edges, v1, v2, weight;//variable for graph(adjacent list)
	int temp,temp2,temp3;//temporary
	double CPUtime,Readtime;
	LARGE_INTEGER startTime,endTime,fre;
	deque< int > LIST;//The dequeue to stroe the current node
	QueryPerformanceFrequency(&fre); //取得CPU頻率
	QueryPerformanceCounter(&startTime); //取得開機到現在經過幾個CPU Cycle
	//read the file network which contain a direct network data
	if( (finput = fopen("network.txt","r")) == NULL)
	{
	cout<<"The file could not be opened!"<<endl;
	exit(0);
	}
	else{
	fscanf(finput,"%d %d",&vertices,&edges);
	}//the end of if-else
	//dynamic memory allocation
	vector< list< pair<int, int> > > adjacencyList(vertices);//adjacent list
	int* inLIST = new int[vertices];//as the bool inLIST[vertices];
	bool* PASS = new bool[vertices];//as the bool PASS[vertices];
	int* d = new int[vertices];//int d[vertices];
	int* pred = new int[vertices];//int pred[vertices]={0};//pred(s)<-0
	int* traversal = new int[vertices];
	//create a file to store the result of calculation of Label correcting algorithm
	if( (foutput = fopen("shortestPath.txt","w")) == NULL)
	{
	cout<<"The file could not be opened!(shorestPath.txt)"<<endl;
	exit(0);
	}
	else{
	for(i=0;i<edges;i++){
	fscanf(finput,"%d %d %d\n",&v1,&v2,&weight);
	adjacencyList[v1].push_back(make_pair(v2, weight));
	}
	cout<<"檔案讀取完畢"<<endl;
	QueryPerformanceCounter(&endTime); //取得開機到讀檔執行完成經過幾個CPU Cycle
	Readtime=((double)endTime.QuadPart-(double)startTime.QuadPart)/fre.QuadPart;
	QueryPerformanceCounter(&startTime);//取得執行演算法前電腦已經過幾個CPU Cycle
	round=0;
	//Initialization
	for(i=0;i<vertices;i++){
	PASS[i]=false;//all node have not been passed
	//false:have not been passed;true:passed
	inLIST[i]=0;//all node are not in LIST(deque)
	d[i]=999999;
	//999999 stand for the infinite
	//d(j)<-infinite for each j(N-{S})
	traversal[i]=0;
	}
	d[0]=0;//d(s)<-0
	pred[0]=0;///pred(s)<-0
	LIST.push_front(0);//LIST<-{s}
	PASS[0]=true;//the node 0 have entered the dequeue(LIST)
	inLIST[0]=1;
	while( !LIST.empty() ){//while LIST != (empty set) then do while loop
	temp=LIST.front();//know what element remove from deque
	LIST.pop_front();//remove first element
	inLIST[temp]--;
	traversal[temp]++;
	round++;
	list< pair<int, int> >::iterator itr = adjacencyList[temp].begin();
	if (adjacencyList[temp].empty()){
	++itr;
	}
	else
	while ( itr != adjacencyList[temp].end()) {//for each arc (i,j) do
	temp2=(*itr).first;//temp2 is j
	temp3=(*itr).second;//temp3 is Cij
	if(d[temp2]>(d[temp]+temp3)){
	d[temp2]=d[temp]+temp3;
	pred[temp2]=temp;
	if( inLIST[temp2]==0 ){//if j not in dequeue then add node to
	//have ever pass should push_front into the dequeue(LIST)
	if(PASS[temp2]==true){//(PASS == true) means passed
	LIST.push_front(temp2);//add node j into deque from the head
	inLIST[temp2]++;
	}else{
	LIST.push_back(temp2);
	inLIST[temp2]++;
	PASS[temp2]=true;
	}
	}//the end of if
	}//the end of if
	++itr;
	}//the end of inner-while
	}//the end of outer-while
	//the end of label-correcting
	for (j=0;j<vertices;j++){
	fprintf(foutput,"%d %d %d\n",j,pred[j],d[j]);
	}
	}
	QueryPerformanceCounter(&endTime); //取得開機到程式執行完成經過幾個CPU Cycle
	CPUtime=((double)endTime.QuadPart-(double)startTime.QuadPart)/fre.QuadPart;
	//output the result
	cout << fixed << setprecision(20) <<"Readtime:"<< Readtime << 's' << endl;
	cout << fixed << setprecision(20) <<"CPU_time:"<< CPUtime << 's' << endl;
	cout <<"Round："<< round <<endl;
	foutput = fopen("traversal_front.txt","w");
	for (j=0;j<vertices;j++){
	fprintf(foutput,"The node %7d traversal times：%d\n",j,traversal[j]);
	}//end write the file
	return 0;//the end of main
	}

view raw shortestPath.cpp hosted with ❤ by GitHub

四、比較與結論

如同前述，我們要比較是否因為依照特殊規定的加入/取出節點，而得到效率。因此我們稍加修改上述程式碼，將取出節點全部改為後端取出，再比較兩者在1.時間效率、2.while迴圈次數、3.各點被走訪次數 ，來知道效率的差異。