acm/course/Shortest_Path
Shortest Path
Single Source Shortest Path
- 若使用Backtracking演算法，將枚舉所有路徑，必會TLE，因此我們將列舉幾項好用DER演算法!!
###Relaxation - 若點v離source的距離為8、點u離source的距離為3，現在有一個點k，(u,k)長度為2、(k,v)長度為1，則對(u,v)做Relax。Relax後點v離source距離更改為6。
###Bellman Ford - 對所有的邊做n-1次的Relax - 時間複雜度：O(VE)
//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);
}- 若有負的cycle，每做一次Relax，source至cycle上點的距離，就會持續變小。
- 偵測辦法：若在第n次做Relax時，若有任何一邊可以被Relax，則有負環存在。
//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() - 相較於BellmanFord做了n-1次Relax，SPFA只對值有改變的點相連的邊做Relax。 - 方法：用Queue存有改變的點。 - 時間複雜度：O(kE)，在k<<V的情況下。 O(VE)，最差的情況。
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次，則有負環存在。
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;
}- 負環的比較：BellmanFord偵測到的負環為整個Graph的，SPFA偵測到的負環為從source出發會走的到的。
All Pair Shortest Path
若用BellmanFord做V次，時間複雜度為O(V^2E)。若用SPFA做V次，時間複雜度為O(kVE)。都可能造成TLE。
###Floyd - 對所有點(i,j)，枚舉所有點k(點i連到點k，點k連到點j)，做Relax。 - 時間複雜度：O(V^3)
