版本 96564a70b5cd5f270c7462ea82bc50777b1f2f4e
Changes from 96564a70b5cd5f270c7462ea82bc50777b1f2f4e to current
Shortest Path
========
Single Source Shortest Path
--------
- <big>若使用Backtracking演算法，將枚舉所有路徑，必會TLE，因此我們將列舉幾項好用DER演算法!!</big>
###Relaxation
- <big>若點v離source的距離為8、點u離source的距離為3，現在有一個點k，(u,k)長度為2、(k,v)長度為1，則對(u,v)做Relax。Relax後點v離source距離更改為6。</big>
~~~{.c }
Relex(u,v,w){
if(dis[u]+w(u,v)<dis[v])
dis[v]=dis[u]+w(u,v);
}
~~~
###Bellman Ford
- <big>對所有的邊做n-1次的Relax</big>
- 時間複雜度：O(VE)
~~~{.c }
//Pseudo Code
BellmanFord(){
//init
dis[source]=0;
for(all i != source)
dis[i] = INF;
//n-1 times
for(i=0;i<n-1;i++)
for(each edge w(u,v) in G)
Relax(u,v,w);
}
~~~
- <big>若有負的cycle，每做一次Relax，source至cycle上點的距離，就會持續變小。</big>
- 偵測辦法：若在第n次做Relax時，若有任何一邊可以被Relax，則有負環存在。
~~~{.c }
//Pseudo Code
BellmanFord(){
//init
dis[source]=0;
for(all i != source)
dis[i] = INF;
//n-1 times
for(i=0;i<n-1;i++)
for(each edge w(u,v) in G)
Relax(u,v,w);
//Negative Cycle
for(each edge w(u,v) in G)
if(dis[u]+w(u,v)<dis[v])
return true;
return false;
}
~~~
###SPFA()
- <big>相較於BellmanFord做了n-1次Relax，SPFA只對值有改變的點相連的邊做Relax。</big>
- 方法：用Queue存有改變的點。
- <big>時間複雜度：O(kE)，在k<<V的情況下。
O(VE)，最差的情況。</big>
~~~{.c }
SPFA(){
for(all i){
dis[i] = INF;
inqueue[i] = false;
}
dis[source]=0;
inqueue[source]=true;
queue.push(source);
while(!queue.empty()){
int now = queue.front();
inqueue[now]=false;
queue.pop();
for(each node v adjacent to now){
if(dis[now]+w(now,v)<dis[v]){
dis[v]=dis[now]+w(now,v);
if(!inqueue[v]){
queue.push(v);
inqueue[v]=true;
}
}
}
}
}
~~~
- 偵測負環：若一個點進去Queue的次數超過n-1次，則有負環存在。
~~~{.c }
SPFA(){
for(all i){
dis[i] = INF;
inqueue[i] = false;
count[i] = 0;
}
dis[source]=0;
inqueue[source]=true;
queue.push(source);
while(!queue.empty()){
int now = queue.front();
inqueue[now]=false;
queue.pop();
for(each node v adjacent to now){
if(dis[now]+w(now,v)<dis[v]){
dis[v]=dis[now]+w(now,v);
if(!inqueue[v]){
queue.push(v);
inqueue[v]=true;
count[v]++;
if(count[v]>=n)
return true;
}
}
}
}
return false;
}
~~~
- <big>負環的比較：BellmanFord偵測到的負環為整個Graph的，SPFA偵測到的負環為從source出發會走的到的。</big>
All Pair Shortest Path
---------
<big>若用BellmanFord做V次，時間複雜度為O(V^2E)。若用SPFA做V次，時間複雜度為O(kVE)。都可能造成TLE。</big>
###Floyd
- <big>對所有點(i,j)，枚舉所有點k(點i連到點k，點k連到點j)，做Relax。</big>
- <big>時間複雜度：O(V^3)</big>
~~~{.c }
Floyd(){
for(i==j)
dis[i][j]=0;
for(each edge w(i,j))
dis[i][j]=w(i,j);
for(not each edge w(i,j))
dis[i][j]=INF;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
~~~
