算法導論實戰（三）（算法導論習題第二十四章）

🌈?個人主頁：十二月的貓-CSDN博客
🔥?系列專欄：?🏀算法啟示錄

💪🏻?十二月的寒冬阻擋不了春天的腳步，十二點的黑夜遮蔽不住黎明的曙光?

前言

第二十四章?

24.1-3

24.1-4

24.2-4

24.3-2?

24.3-3

24.3-6

24.3-8

24.3-10?

總結

前言

算法導論的知識點學習將持續性更新在算法啟示錄_十二月的貓的博客-CSDN博客，歡迎大家訂閱呀（反正是免費的哦~~）

實戰篇也將在專欄上持續更新，主要目的是強化對理論的學習（題目來源：山東大學孔凡玉老師推薦）

第二十四章?

24.1-3

問題描述：

假設給定G=(V,E)是一帶權重且沒有權重為負值的環路的有向圖，對于所有的結點𝑣∈𝑉，從源結點s到結點v之間的最短路徑中，包含邊的條數的最大值為m。請對算法BELLMAN-FORD進行簡單修改，可以讓其在m+1遍松弛操作之后終止，即使m不是事先知道的一個數值。

問題分析：

如果一個圖所有節點到源點s的距離包含的邊的條數的最大值為m，那么意味算法在進行m輪松弛后，整個圖的所有節點都已經得到最短路徑。此時不再需要繼續執行m+1輪松弛

問題求解：
在BELLMAN-FORD算法的2-4行的執行記錄下松弛前各點的最短路徑長度，如果某一次松弛循環結束時所有v.d的值跟本次循環開始時v.d的值相比不發生改變時，此次循環即為第m+1次。?

INITALIZE-SINGLE-SOURCE(G,s)
for i=1 to |G.V|-1for each v in G.Vsave v.d to Tfor each edge(u,v) in G.ERELAX(u,v,w)for each v in G.Vif v.d != T[v].dcontinue //沒有點的值被更新，說明所有點都取到最短路徑，則停止for each edge(u,v) in G.Eif v.d>u.d+w(u,v)return FALSEreturn TRUE

24.1-4

問題描述：
修改Bellman-Ford算法，使其對于所有結點v來說，如果從源結點s都結點v的一條路徑上存在權重為負值的環路，則將v.d的值設置為?∞。

問題分析：

貝爾曼福德算法不能夠處理存在權重為負值的環路，因為一旦存在則會一直在環路上循環，因為這樣的最短路徑值會不停縮短。該情況顯然是我們不希望發生的，所以我們增加這一個功能來應對存在負值環路的特殊情況。

問題求解：

如果存在負權環路，那么w(u,v)就是無窮小，并且w（s,v)（就是v.d)也是無窮小，于是這個if語句返回值是FLASE。所以只要在if內增加對v.d的修正即可

INITALIZE-SINGLE-SOURCE(G,s)
for i=1 to |G.V|-1for each v in G.Vsave v.d to Tfor each edge(u,v) in G.ERELAX(u,v,w)for each v in G.Vif v.d != T[v].dcontinue //沒有點的值被更新，說明所有點都取到最短路徑，則停止for each edge(u,v) in G.Eif v.d>u.d+w(u,v)v.d=-∞return FALSEreturn TRUE

24.2-4

問題描述：

給出一個有效的算法來計算一個有向無環圖中的點的路徑總數。分析你自己的算法。

問題分析：

目前我們手頭關于圖的知識點只有圖的基本算法+最短路徑算法+最小生成樹，利用這些知識點來思考如何找路徑總數。考慮到本題不用考慮有權圖，所以我們把眼光轉向BFS和DFS兩個算法。進一步思考，我們能知道BFS常常用在求解最短路徑算法中（BFS特點在于得到的是一棵樹，同時每個點都是最短路徑的），在這里我們需要求解的是到一個點的所有路徑。

假如我們有如下一個圖，現在要我們來求解頂點6的路徑數

樸素想法：我們最樸素的想法就是從頂點1、2、3、5、4、....、這樣的順序去求解路徑數。于是我們可以得到p(1)=1; p(2)+=p(1); p(3)+=p(1); p(5)+=p(2); p(4)+=p(2); 等等。

總的來說，就是從上層到下層計算，下層的路徑數：下層路徑數+=上層路徑數

那什么是下層？什么又是上層呢？

下層：在上層結點撤去后不存在入度結點的點；上層：存在出度給其他頂點

如果可以從上層到下層計算呢？我們就需要對圖進行拓撲排序

拓撲排序：是一種對有向圖進行排序的算法，其主要目的是確定圖中節點的線性順序，使得在排序后，所有的邊都從左到右指向更大的節點。換句話說，拓撲排序可以將圖中的節點按照其依賴關系進行排序，使得所有的依賴關系都被滿足。

?實現拓撲排序的方法有兩個：一、計算結點入度+隊列方法（通用方法）二、深度搜索（用于無環路的有向圖）

本題是有向無環圖可以用方法二

問題求解：

一、利用DFS搜索樹，將圖進行拓撲排序，得到拓撲排序后的圖

二、在新的圖中，按照拓撲排序的順序，對每個點u，找其所指向的點v，執行v.paths+=u.paths

PATHS(G)topologically sort the vertices of Gfor each vertex u, taken in topologically sorted orderfor each v ∈ G.Adj[u]v.paths = u.paths + v.pathsreturn the sum of all paths attributes

24.3-2?

問題描述：

請舉出一個包含負權重的有向圖，使得 Dijkstra 算法在其上運行時將產生不正確的結果。為什么在有負權重的情況下，定理 24.6 的證明不能成立呢？

問題分析：

看到對本題的其中一個解答：?

大致意思是說：如果存在負權重回路，那么這個RELAX操作是沒有意義的，因為RELEX是有限次的，但是通過負權重回路，我們到任何通過這個回路的點的距離都是?∞。于是在RELAX后，u.d并不是（s，u）的最小值，因此不成立

顯然上面的證明是沒有問題的，但是本題問的是為什么不能有負權重邊，而不是負權重回路。所以僅僅有上面的證明是不充分的

問題求解：

Dijkstra算法是貪心貪心算法，也就是說每次都選擇貪心策略下的局部最優解，這個解在后續中也不會再修正。那么對于如下的帶有負權重的有向圖：

假如源點是A，那么首先選擇C此時C值為1；后選擇B此時B的值為2，然后又會選擇C此時C的值應該要修正為0.但是C的值不會被修正，因此Dijkstra每個點只訪問一次（貪心策略）。所以最終C.d=1，但是實際上C到A的最小值為0。因此定理 24.6是不成立的，算法結束后，存在點的d的值不是最短路徑值

24.3-3

問題描述：

假定將 Dijkstra 算法的第行改為：

4 ：white（lQl）>1

這種改變將讓呻證循環的執行次數從 IVI 次降低到 IVI -1次。這樣修改后的算法正確嗎？

問題分析：

迪杰斯特拉算法最后得到的結果有兩個：一、訪問序列s，用來記錄對點的訪問次序；二、每個點的v.d記錄每個點到源點的距離。

所以正確性的證明也將從這兩個角度展開：

問題求解：

正確的！

一、假如我們已經得到前面V-1個點的訪問序列，那么最后一個點不需要放入，我們也可以只知道最終的訪問序列

二、迪杰斯特拉對每個結點只訪問一次，且每次都能確定一個點的最短路徑，此時程序運行了V-1個循環，訪問并確定了V-1個點的最短路徑。所以最后一個點進行松弛操作時，它并不能縮短其他點到原點的距離，所以最后一個點的RELAX操作也是無意義的。因此算法是正確的

24.3-6

問題描述：

問題分析：?

本題和最短路徑問題存在幾點不一樣：

一、它需要找的是最可靠，也就是值最大的路徑，可以認為是最長路徑；

二、最短路徑算法相連路徑段之間的關系是求和，但是通信鏈路相連路徑段求可靠性時之間的關系是求積

問題求解：

一、最長路徑。那就把貪婪準則改為選擇d最大的點

二、總路徑和子路徑的關系變為乘。那就修改RELAX準則，從+變為*

三、初始化。源點可靠性為1；其他未搜索到的點初始化為0

INITIALIZE(G,s)for each vertex v ∈ G.Vv.d=0v.π=NULLs.d=1
DIJKSTRA(G,w,s) //s用來記錄訪問的順序，是需要返回的值；w邊的權重集合S=空集合Q=G.Vwhile(Q <> 空集合）u=EXTRACT-MAX(Q)S=S U {u}for each vertex v∈G.adj[u]RELEX(u,v,w) 
RELAX(u,v,w)if v.d<u.d*w(u,v)v.d=u.d*w(u,v)v.π=u

24.3-8

問題描述：

問題分析：

我第一次看這道題的時候，說實話，連題目都沒看懂【emmmmm】。具體原因就在權重函數w：E->{0,1,...,W}這里沒看明白。

這個權重函數就表示：邊E的權重只能取{1,2,....,W}中的數

再來看看這個WV時間復雜度是哪里來的？要解決這個問題

先讓友友們先思考另一個問題：WV含義是什么？

WV含義：圖中任意點到源點的距離上限（圖中任意點到源點的距離不超過WV）

再來思考一個這個E的時間復雜度含義又是什么？

E是指邊，也就是說我需要對邊進行E次操作，這不禁讓我們想到了松弛操作。

E的復雜度就代表我們要對所有邊進行一輪的松弛，每次松弛邊本質是更新點的V.d，所以本質就是對點進行了E次的操作

問題求解：

從優化“貪心尋找dist最小點”的操作入手。由于邊權≤W≤𝑊，那么一個點的dist值不會超過VW。基于這個條件，我們可以抽象出一個長度為VW的隊列數組。每個數組的隊列存儲著“dist值為該數組序號”的點。然后抽象出一個指針，這個指針指向的隊列，是我們貪心取點的隊列。由于一個點被取出后，被他更新的點只會被push進該隊列或者該隊列之后的隊列，所以指針只會從左到右掃描一遍數組。

最多掃描一遍數組，復雜度為O(VW）。此外，最多會有E次入隊、出隊操作，復雜度為O(E)。總時間復雜度為O(VW+E)。

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = ..., M = ..., W = ...;
queue<int> qs[N*W];
int head[N], ver[M], edge[M], Next[M], tot = 0;//采用數組模擬鄰接鏈表的方式
void add(int x,int y,int z){ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
int d[N], v[N];
int n, m, w;
void dijkstra(int s){memset(d,0x3f,sizeof(d));//初始化為正無窮memset(v,0,sizeof(v));d[s] = 0; qs[0].push(s);for(int k = 0; k<=n*w; k++){while(!qs[k].empty()){int x = qs[k].front(); qs[k].pop();if(v[x]) continue;v[x] = 1;for(int i = head[x]; i; i = Next[i]){int y = ver[i], z = edge[i];if(d[y] > d[x] + z){d[y] = d[x] + z;qs[d[y]].push(y);}}}}
}

24.3-10?

問題描述：

假設給定帶權重的有向圖 G=(V, E), 從源結點s發出的邊的權重可以為負值，而其他所有邊的權重全部是非負值，同時，圖中不包含權重為負值的環路。證明： Dijkstra 算法可以正確計算出從源結點到所有其他結點之間的最短路徑。?

問題分析：

證明Dijkstra 算法是可行的==證明一個貪心策略是有效的。考慮到Dijkstra 算法本身的貪心策略已經證明結束，所以我們只需要針對其中變化的部分進行特別論證即可

特別部分：從源結點s發出的邊的權重可以為負值

利用?Dijkstra 算法取出S，并更新與S相鄰的點，將得到多個值不為0的點

于是，該問題可以等效為：多源點且初始值不為0的最短路徑問題，并且每個源點都可以適用Dijkstra 算法

因此，整個問題同樣可以利用?Dijkstra 算法來求解

問題求解：

首先，Dijkstra的算法思路是：對于任意一個從隊列取出來的點x，如果它沒有被標記過，那么d[x]一定是源結點s到x的最短路徑，然后我們不斷地進行貪心擴展，最終可以得到源結點s到每個結點的最短路徑。它的本質是一個貪心+BFS算法。
現在，題目中給出的限制是：“只有從源結點s出發的邊權重可以為負，且圖中無負環”。
源結點s一定是在一開始被取出，更新完之后被丟棄。因為只有源結點s出發的邊權重可以為負，所以我們在后面更新由“s以外的其他點”更新“s以外的其他點”時，仍舊是在一個無負邊權的圖中的更新，所以Dijkstra仍正確。而對于這些點，當他們嘗試更新s的時候，因為圖中無負環，所以無法更新s。此外，由于無負環，s也不會出現有一個權值為負的子環無限更新自身的情況。綜上，Dijkstra基于貪心的性質沒有發生改變，每次從隊列中取出的一個點更新完其他點被丟棄后，這個點在后面一定不會被更新。所以Dijkstra仍舊可以正確運行。