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。

Relex(u,v,w){
   if(dis[u]+w(u,v)<dis[v])
       dis[v]=dis[u]+w(u,v);
}

###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存有改變的點。 ~{.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; } } } } }~