1. 首頁 > 生活百科 > >

Day3 最短路 最小生成樹 拓撲排序

生活百科

Day3 最短路 最小生成樹 拓撲排序（一）最短路一、多源最短路【Day3 最短路 最小生成樹 拓撲排序】從任意點出發到任意點的最短路
1. Floyd\(O(n^3)\)for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)Edge[i][j]=min(Edge[i][j],Edge[i][k]+Edge[k][j]);2. 拓展：傳遞閉包在圖中，給定若干元素和若干對二元關系，且關系具有傳遞性 ?！巴ㄟ^傳遞性推導出盡量多的元素之間的關系”的問題稱為傳遞閉包 。
傳遞性：設 \(\odot\) 是定義在集合 \(S\) 上的二元關系，若對于任意 \(a,b,c \in S\) ， 只要有 \(a \odot b\) 且 \(b \odot c\)，就必然有 \(a \odot c\)，則稱關系 \(\odot\) 具有傳遞性
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)can[i][j]|=can[i][k]&can[k][j];二、單源最短路從一個點出發到所有點的最短路
1. Dijkstra①Dijkstra\(O(n^2)\)void dijkstra(int x){ for(int i=1;i<=t;i++)dis[i]=INF; dis[x]=0,vis[x]=true; for(int i=Link[x];i!=0;i=Edge[i].nxt) {int y=Edge[i].y;dis[y]=Edge[i].vis; } for(int i=1;i<=t;i++) {int f,minn=INF+10;for(int j=1;j<=t;j++){if(!vis[j]&&dis[j]<minn){minn=dis[j];f=j;}}vis[f]=true;for(int i=Link[f];i!=0;i=Edge[i].nxt){int y=Edge[i].y;if(!vis[y]) dis[y]=min(dis[y],Edge[i].vis+dis[f]);} }}②堆優化 Dijkstra\(O(m \log n)\)priority_queue<node> q;bool operator < (node n1,node n2){ return n1.dis>n2.dis;}void dijkstra(int st){ for(int i=1;i<=n;i++)dis[i]=INF; dis[st]=0; q.push({0,st}); while(!q.empty()) {int x=q.top().i;q.pop();if(vis[x]) continue;vis[x]=1;for(int j=Link[x];j!=0;j=Edge[j].nxt){int y=Edge[j].y,val=Edge[j].val;if((long long)dis[x]+val<dis[y]){dis[y]=dis[x]+val;q.push({dis[y],y});}} }}2. SPFA\(O(km \sim nm)\)解決負環判斷/差分約束問題 。
void SPFA(int st){ queue<int> q; for(int i=1;i<=n;i++)dis[i]=INF;dis[st]=0; q.push(st); while(!q.empty()) {int x=q.front();q.pop();vis[x]=false;for(int i=Link[x];i;i=Edge[i].nxt){int y=Edge[i].y,val=Edge[i].val;if(dis[x]+val<dis[y]){dis[y]=dis[x]+val;if(!vis[y]){q.push(y);vis[y]=1;}}} }}3. 拓展：查分約束差分約束系統是一種特殊的 \(N\) 元一次不等式組 。
它包含 \(N\) 個變量 \(X_1 \sim X_N\) 以及 \(M\) 個約束條件，每個約束條件都是由兩個變量作差構成的，形如 \(X_i-X_j \leq C_k\) ，其中 \(C_k\) 是常數 。我們要解決的問題是：
求一組解 \(X_1 = a_1,X_2 = a_2,\cdots, X_N = a_N\)，使得所有約束條件得到滿足 。
我們把不等式 \(X_i-X_j\leq C_k\) 變為 \(X_i\leq X_j+C_k\)  ， 這和我們單源最短路里 \(dis[y]\leq dis[x]+z\) 非常相似 。
**因此，可以把 \(X_i\) 看作有向圖中的一個點 \(i\)，對于每個條件 \(X_i-X_j\leq C_k\) ， 從節點 \(j\) 向節點 \(i\)，連一條長度為 \(C_k\) 的有向邊 。**
如果 \(a_1,a_2,\cdots,a_n\) 是該差分約束系統的一組解，那么對于任意的常數 \(D\)，\(a_1+D,\cdots,a_n+D\) 顯然也是該差分約束系統的一組解，因為這樣做差后 \(D\) 剛好被消掉 。
所以不妨先求一組負數解，假設 \(\forall x_i\leq 0\) ，添加一個 \(0\) 號節點，\(x_0=0\)，即有 \(x_i-x_0\leq 0\)，
設 \(dis[0]=0\) ， 從 \(0\) 開始跑單源最短路，若圖中存在負環，則給定的差分約束系統無解；否則， \(x_i=dis_i\) 為該差分約束系統的一組解 。

    推薦閱讀