寫在前面的話：寫寫復習下它，太久沒怎么寫這類題了
文章部分內容出自《演算法競賽進階指南》
單源最短路徑
這種問題就是說給一張有向圖，以某一個節點（一般為1號節點），記錄下其他每一個點
到達這個1號節點的最短路徑的長度，
常用演算法：Dijkstra，Bellman-Ford，SPFA(本質上是Bellman-Ford）
Dijkstra演算法
基本思路：
它是基于貪心演算法的一種方案，只能用在所有邊長度非負的圖，因為若z為負，全域最小值不可能被其他點
更新了，其中，第一步選出來的x已經滿足--dist[x]是起點到x點的最短路徑，本質上，我們在不斷尋找全域
最小值在進行標記和拓展，最后就得到起點1到每個節點的最短路，
程序：
1.初始化dist[i]陣列，即原點到i點的距離，dist[1]=0，其他點初始化到原點距離為+∞；
2.找出一個未被標記的且dist[x]最小的點x，再標記節點x；
3.掃描x的所有出邊，若dist[y]>dist[x]+z,就更新dist[y] = dist[x]+z；
4.重復2--3，直到所有點被標記為止
當然我們可以發現，在找全域最小值的時候，代碼可以繼續優化，即找這個最小值可以用二叉堆去找，
復雜度從O($n^{2}$) 進化成 O($m log n$)，
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const long MAXN=1000010;
long n,m;
long head[MAXN],Next[MAXN],ver[MAXN],edge[MAXN],tot=0;
priority_queue< pair<long,long> > q;
inline void add(long x,long y,long z){
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
bool v[MAXN];
long dist[MAXN];
inline void dijkstra(){
for(long i=1;i<=n;i++) dist[i]=999999;
memset(v,0,sizeof v);
dist[1]=0;
q.push(make_pair(0,1));
while(q.size()){
long x=q.top().second;
q.pop();
if(v[x]) continue;
v[x]=1;
for(long i=head[x];i;i=Next[i])
{
long y=ver[i],z=edge[i];
if(dist[y]>dist[x]+z){
dist[y]=dist[x]+z;
q.push(make_pair(-dist[y],y));
}
}
}
}
int main(){
scanf("%ld%ld",&n,&m);
long x,y,z;
for(long i=1;i<=m;i++){
scanf("%ld%ld%ld",&x,&y,&z);
add(x,y,z);
}
dijkstra();
for(long i=1;i<=n;i++)
printf("%ld\n",dist[i]);
}
Bellman-Ford演算法
基本思路
它是基于迭代的思想去考慮，即使所有邊(x,y,z)滿足三角形不等式：d[y]<=d[x]+z
如下圖：
程序：
1.掃描所有邊，若dist[y]>dist[x]+z,就使dist[y]=dist[x]+z；
2.重復上述步驟直到沒有更新發生為止，
復雜度高達O(nm)，但它優于dijkstra的一點，是它的邊權可以為負值，
SPFA演算法
基本思路：
spfa在國際上通稱”佇列優化的Bellman-Ford演算法“，它用佇列保存了待擴展的節點，每一次的入隊
相當于完成一次更新，使得節點慢慢收斂，即松弛，稀疏圖效率高，
因為對于一個從x到y的邊，節點x還沒有松弛過，那y就沒必要松弛，所以我們用佇列記錄松弛過的點，
避免了bellman-ford中的冗余松弛操作，
程序：
1.建立一個佇列，初始入隊節點1；
2.取出隊頭，并掃描所有出邊，若dist[y]>dist[x]+z,則更新dist[y]=dist[x]+z,并判斷y是否在佇列中，若
不在，則將y入隊；
3.重復上述步驟直至佇列為空，
用簡略語言概述就是，我們有一個松弛點x，嘗試x能到達的點y，若y可以被松弛，就更新dist[y]，在
這個條件下，若y還沒入隊，那就把這個松馳過的點入隊，直到佇列為空，
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const long MAXN=1000010;
long n,m;
long head[MAXN],Next[MAXN],ver[MAXN],edge[MAXN],tot=0;
queue <long> q;
inline void add(long x,long y,long z){
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
bool v[MAXN];
long dist[MAXN];
inline void spfa(){
for(long i=1;i<=n;i++) dist[i]=999999;
memset(v,0,sizeof v);
dist[1]=0;
q.push(1);
v[1]=1;
while(q.size()){
long x=q.front();
q.pop();
v[x]=0;
for(long i=head[x];i;i=Next[i])
{
long y=ver[i],z=edge[i];
if(dist[y]>dist[x]+z){
dist[y]=dist[x]+z;
if(v[y]==0) q.push(y),v[y]=1;
}
}
}
}
int main(){
scanf("%ld%ld",&n,&m);
long x,y,z;
for(long i=1;i<=m;i++){
scanf("%ld%ld%ld",&x,&y,&z);
add(x,y,z);
}
spfa();
for(long i=1;i<=n;i++)
printf("%ld\n",dist[i]);
}
特別地，當我們要去判定負環的時候，我們可以用一個陣列c[i]表示1到i的最短路徑上點的個數，每一次松弛x-y時，
我們就用c[y]=c[x]+1,當c[y]>n時，即存在負環，
注：
其實對比dijkstra和spfa，我們可以發現，dijkstra針對每一個最小距離點進行擴展，
而spfa則是通過迭代思想將所有邊進行擴展，自然spfa的復雜度會高于dijkstra，但是spfa同時也具有
可以更加容易加入各種其他演算法和對負權的邊，負環的處理，
溫馨提示，面對一個不存在負權邊的圖最好用dijkstra，因為spfa易被惡意卡掉，
任意兩點間的最短路徑
Floyd演算法
基本思路：
它是一種基于動態規劃的演算法，我們可以用D[k,i,j]來表示i經過編號不超過k的節點后到達j的最短路，所以
我們可以將其劃分為兩個子問題，一是congi經過編號不超過k-1的節點到j，或者從i經過k節點到達j，
則 D[k,i,j]=min(D[k-1,i,j],D[k-1,i,k]+D[k-1,k,j])
所以k是階段，應該放在最外層
我們也可以用D保存鄰接矩陣，省略k這一維，即：
D[i,j]=min(D[i,j],D[i,k]+D[k,j])
也可以理解為從i到j，看看目前的情況好，還是再經過一個中間點k更好，
程序：
這就不再贅述了，太過簡單......
#include<iostream>
#include<cmath>
using namespace std;
const long MAXN=10010;
long dist[MAXN][MAXN];
long n,m;
int main(){
cin>>n>>m;
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
dist[i][j]=999999;
for(long i=1;i<=n;i++)
d[i][i]=0;
long x,y,z;
for(long i=1;i<=m;i++){
cin>>x>>y>>z;
if(dist[x][y]>z) dist[x][y]=z;
}
for(long k=1;k<=n;k++)
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(long i=1;i<=n;i++){
for(long j=1;j<=n;j++)
cout<<dist[i][j]<<" ";
cout<<endl;
}
}
范圍，數值最大值可以自行更改
傳遞閉包
在交際網路中存在若干元素和若干對二元關系，關系具有傳遞性，請推匯出盡量多的元素間的關系----傳遞閉包
易得，我們可以用floyd解決此類問題
#include<iostream>
#include<cmath>
using namespace std;
const long MAXN=10010;
bool dist[MAXN][MAXN];
long n,m;
int main(){
cin>>n>>m;
for(long i=1;i<=n;i++)
dist[i][i]=1;
long x,y,z;
for(long i=1;i<=m;i++){
cin>>x>>y;
dist[x][y]=dist[y][x]=1;
}
for(long k=1;k<=n;k++)
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
dist[i][j]|=dist[i][k]&dist[k][j];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14496.html
標籤：其他
上一篇：jQuery---淘寶精品案例