圖論小專題A

圖的儲存和最短路算法。

大意失荊州。今天考試一到可以用Dijkstra水過的題目我竟然沒有做出來，這說明基礎還是相當重要?？紤]到我連Tarjan算法都不太記得了，我決定再過一遍藍皮書，對圖論做一個小的總結。圖論這個部分可能會分幾次發布出來。

0 圖的儲存

一般而言，在代碼中我們會用\(M\)表示邊的個數，\(N\)表示點的個數。

鄰接矩陣：用一個矩陣\(A_{ij}\)表示點\(i,j\)的距離或連通性。
鄰接表：用vector類型edge儲存。其中edge[i][j]表示以\(i\)為起點的第\(j\)條邊。
鏈式前向星：非常重要的一種儲存方式。是一種類似“哈希表”的結構，其中用head記錄每個點對應的邊鏈表的表頭，每個邊記錄邊鏈表的下一條邊。

無向邊可以用兩條方向相反的有向邊代替。

1 最短路

1.1 單源最短路問題(SSSP，Single Source Shortest Path)

對于任意一個點\(i\)，求其到某一個固定點的距離\(dis_i\)。

在求解最短路問題中，有一個核心的“松弛操作relax”：

\[ d(i,j) =\min\{d(i,j), d(i,k)+d(k,j)\} \]

它是所有SSSP算法的基礎。
如果有\(d(i,j)>d(i,k)+d(k,j)\)，我們就說\(k\)能松弛\((i,j)\)。

Dijkstra算法
貪心算法。其使用條件是沒有負邊。
這里采用了一個貪心的策略：注意到全局最優的SP是不可能再被松弛的，否則就跟這個性質不符了。我們每次就用這個最優的SP去松弛其他的SP，從而使得每一個SP都逐步變得最優，即不可松弛。

這個算法的代碼如下：

inline void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(used, 0, sizeof(used));
	
	dis[S] = 0;
	
	while(1)
	{
		int transferNode = getTransferNode();
		if(transferNode == -1)
			return;
		
		for(rg int e = head[transferNode]; e; e = edge[e].next)
		{
			int to = edge[e].to;
			checkMin(dis[to], dis[transferNode] + edge[e].len);//用最小值更新dis[to]
		}
		
		used[transferNode] = true;
	}
}

其中getTransferNode()是找到dis最小的中轉點。

inline int getTransferNode()
{
	int transferNode = -1;
	number disMin = Inf;//number 是typedef過的long long 
	for(rg int i = 1; i <= N; ++ i)
	{
		if(!used[i] && dis[i] < disMin)
		{
			disMin = dis[i]; 
			transferNode = i;
		}
	}
	return transferNode;
}

由于要枚舉中轉點和每個與中轉點相連的點，上面代碼的時間復雜度是\(O(N^2)\)的。
當然，我們也可以用二叉堆(priority_queue)來維護\(dis\)數組。這樣可以在\(O(N\log N)\)的時間內完成算法。上述getTransferNode部分代碼如下：

priority_queue< pair<number, int> > heap;
inline int getTransferNode()
{
	int transferNode = -1;
	while(heap.size() > 0)
	{
		transferNode = heap.top().second;
		heap.pop();
		if(used[transferNode])
			continue;
		used[transferNode] = true;
		return transferNode;
	}
	return -1;
}

主過程代碼如下：

inline void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(used, 0, sizeof(used));
	
	dis[S] = 0;
	heap.push(make_pair(0, S));
	
	while(1)
	{
		int transferNode = getTransferNode();
		if(transferNode == -1)
			return;
		
		for(rg int e = head[transferNode]; e; e = edge[e].next)
		{
			int to = edge[e].to;
			if(dis[to] > dis[transferNode] + edge[e].len)
			{
				dis[to] = dis[transferNode] + edge[e].len;
				heap.push(make_pair(-dis[to], to));
			}
		}
		
		used[transferNode] = true;
	}
}

Bellman-Ford和SPFA
由于負邊權會導致\(dis_i>dis_j+d(j,i)\)，最小的\(dis\)反而可能會更新出一個比它更小的\(dis\)。這樣，一個點可能會不斷被更新，這個全局最優的貪心策略就不成立了。
在之前的Dijkstra算法上，我們再考慮如何進一步優化。
如果對于任意的邊\((i,j)\)，均有\(dis_i\leq dis_j+d(i,j)\)，那么這個\(dis\)就是所求的答案。這個不等式叫做三角形不等式。因此，我們可以考慮這樣一種做法：我們由“點松弛”變為“邊松弛”，使得每條邊滿足三角型不等式。
Bellman-Ford的算法流程大致就是：不斷地掃描并更新每一條邊，使得每一條邊都滿足三角形不等式，直到沒有邊可以再更新。

由于Bellman-Ford算法是固定的\(O(NM)\)，在實際運行上速度有時不如Dijkstra，這里就不張貼這個代碼了。我們考慮隊列優化版的Bellman-Ford算法：SPFA(Shortest Path Fast Algorithm)算法。這個算法的命名其實和“快速排序”這個名字一樣一根筋。正因如此，SPFA這個名字只在中國流行。

仔細想想，根據Dijkstra算法的推論，是不是只有全局最優值才能更新其他值？我們可以類似地，每次只對剛更新完的\(dis\)點所相連的邊進行松弛。我們可以考慮建立一個隊列，當一個節點被更新之后，就將其加入隊列，并在之后考慮它所相連的邊是否能被更新。

由于每一次入隊和出隊都代表一次邊的更新，而一個節點可能入隊出隊若干次，故算法的時間復雜度下限為\(\Omega(M)\)，上限為\(O(MN)\)。
算法的代碼如下：

queue<int> q;
bool state[maxN];
#define IN_QUEUE true
#define NOT_IN_QUEUE false
inline void SPFA()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(state, NOT_IN_QUEUE, sizeof(state));
	
	dis[S] = 0; state[S] = IN_QUEUE; q.push(S);
	while(!q.empty())
	{
		int cur = q.front(); q.pop();
		state[cur] = NOT_IN_QUEUE;
		for(rg int e = head[cur]; e; e = edge[e].next)
		{
			int to = edge[e].to;
			if(dis[to] > dis[cur] + edge[e].len)
			{
				dis[to] = dis[cur] + edge[e].len;
				if(state[to] == NOT_IN_QUEUE)
				{
					state[to] = IN_QUEUE;
					q.push(to);
				}
			}
		}
	}
}
#undef IN_QUEUE
#undef NOT_IN_QUEUE

SPFA算法接近上界的條件是圖是疏密圖或網格圖。如果圖中沒有負邊權，我們可以用優先隊列隊優化這個算法。此時算法時間復雜度是比較穩定的\(O(M\log N)\)，但是往往就不如Dijkstra優了。
在實際應用的過程中，要根據實際條件判斷如何使用。圖中往往有樣例數據、數據范圍、子任務等要素?？梢酝ㄟ^這些來判斷圖是否稀疏，從而分門別類地使用對應算法。

SPFA算法的一大優勢在于可以判斷是否有負環。根據\(O(NM)\)的時間復雜度上限可以知道，如果一個點被更新大于等于\(n\)次，說明這個圖一定存在負環。此時存在一條無窮小的路徑，SSSP也就沒有意義了。

1.2 最短路衍生算法

SPFA的過程也可以用dfs實現。但是顯然的，由于SPFA往往需要對若干個點更新多次，如果使用dfs，不僅可能會超時，還有可能因迭代過多而發生棧溢出。但是，dfs的SPFA有一個非常明顯的長處：找負環。
和bfs的做法不同，我們將隊列改為棧，每次將當前節點入棧，搜索完后將當前節點出棧。只有可以被松弛的節點才有搜索的必要。
代碼很簡單，如下：

queue<int> q;
bool state[maxN];
#define IN_STACK true
#define NOT_IN_STACK false
inline bool SPFA(int curNode)
{
	state[curNode] = IN_STACK;
	for(rg int e = head[curNode]; e; e = edge[e].next)
	{
		int to = edge[e].to;
		if(dis[to] > dis[curNode] + edge[e].len)
		{
			dis[to] = dis[curNode] + edge[e].len;
				if(state[to] == IN_STACK || SPFA(to) == true)
					return true;
		}
	}
	state[curNode] = NOT_IN_STACK;
	return false;
}

再主程序中對每一個節點進行一次SPFA，直到找到負環為止。

對于隨機圖，我們可以先運行一個SPFA_INIT：首先選定一個初始點，每次擴展到一個節點時，隨機地選擇一條可松弛的邊進行下一步擴展；如果不存在可松弛邊，就結束這一過程。
對每個點進行一次SPFA_INIT，然后再用SPFA對每個點進行擴展，這樣效率會有所提高。

更近一步的，我們還可以使用一個IDFS_SPFA，即加深迭代搜索。每次選取搜索的深度分別為\(1,2,4,8,16,\cdots\)是一個不錯的選擇。這些過程都比較簡單，就是在原代碼上進行簡單的改裝。代碼就不再粘貼。

1.3 多源最短路徑算法（MSSP）

Floyd算法

非常經典的算法。其實質是動態規劃算法。

通過類比，我們發現松弛操作\(d(i,j)=\min\{d(i,j),d(i,k)+d(k,j)\}\)與區間DP十分類似。這意味著\(i\)和\(j\)兩個狀態變量不適合用來劃分階段。

我們設\(F(k,i,j)\)表示以\(1,2,\cdots,k\)點作為中轉點，\(i,j\)之間的最短距離。我們可以在選前\(k-1\)個點的基礎上，選擇第\(k\)個點，并看其是否更優。有方程：

\[ F(k,i,j)=\min\{F(k - 1,i,j), F(k - 1,i,k)+F(k - 1,k,j)\} \]

注意這個方程滿足兩個性質：

轉移\(F(k,i,j)=F(k-1,i,j)\)成立。
第\(k\)階段剛計算出的狀態量\((i,j)\)不會被再次引用。
由此，我們可以刪去\(k\)維，得到狀態轉移方程：

\[ F(i,j)=\min\{F(i,j), F(i,k)+F(k,j)\} \]

注意這里\(k\)是階段，要放在最外層循環。最后可以算出任意兩點的最短路。
有\(N\)個階段，每個階段\(N^2\)個狀態，所以轉移的時間復雜度為\(O(N^3)\)。

Floyd算法還可以判斷點的連通性：只要把狀態表示成\(F(k,i,j)\)表示成“以前\(k\)個點為中轉點，能否讓\(i,j\)連通”。轉移方程同理進行對應修改即可。這個問題和“傳遞閉包”有關，“閉包”的概念可以在網絡上或者離散數學教材上找到，并不是一個很高深的概念。

Dijkstra算法？
從理論上來講，可以用\(dis_{i,j}\)表示以\(i\)為源點，\(j\)到源點的最短路，然后做\(N\)次Dijkstra算法。如果采用二叉堆優化，理論上可以用\(O(N^2\log N)\)的時間完成處理。但是至于為什么在網絡上并沒有有關介紹，是常數原因還是其他？我本人也不清楚。如果有哪位大佬知道原因或者做過有關測試，歡迎在下方留言。

posted @ 2019-08-06 15:05 LinearODE 閱讀(276) 評論(0) 收藏舉報

刷新頁面返回頂部

JasonZhou

且放白鹿青崖間