分享到plurk 分享到twitter 分享到facebook

版本 41d69d6d7d9c6df6ed207584af0bddb3e4aeff7f

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。

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) ###SPFA()

All Pair Shortest Path

###Floyd