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

版本 d126ae21b67dc1eddd35032d4abf4dcd17cbd9d1

acm/course/Shortest_Path

Changes from d126ae21b67dc1eddd35032d4abf4dcd17cbd9d1 to 39a2061170207b95182a1bc68ebef497a907f849

Shortest Path
========
Single Source Shortest Path
--------
- <big>若使用Backtracking演算法,將枚舉所有路徑,必會TLE,因此我們將列舉幾項好用DER演算法!!</big>

![](/acm/13125075_944400135668382_1681010432_n.gif)


###Relaxation
- <big>若點v離source的距離為8、點u離source的距離為3,現在有一個點k,(u,k)長度為2、(k,v)長度為1,則對(u,v)做Relax。Relax後點v離source距離更改為6。</big>

![](/acm/Relax.png)
~~{.c }

~~~{.c }
Relex(u,v,w){
   if(dis[u]+w(u,v)<dis[v])
       dis[v]=dis[u]+w(u,v);
}
~~~
###Bellman Ford
###SPFA()

All Pair Shortest Path
---------
###Floyd