] 寫一點我對最短路徑算法的了解
最短路徑算法的作用就是在圖中找出任意兩點間最短距離的途徑，比如可以在地圖上找出任兩個城市之間路程最短的那條路徑。
具體運用請見：
http://www.hartech.cn/blog/blogview.asp?logID=52
圖的四種算法的界面圖形示範：
http://www.hartech.cn/blog/blogview.asp?logID=88
有兩種算法可以實作，一種是迪傑斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。
迪傑斯特拉（Dijkstra）算法：
（給出一個出發點，可算出該出發點到所有其它點的最短距離還有具體路徑）
算法過程：
一，用D[v]記錄任一點v到出發點的最短距離，建立一S集合且為空，用以記錄已找出最短距離的點。
二，掃描非S集中D[]值最小的節點D[w]，也就是找出下一條最短路徑，把節點w加入S集中。
三，更新所有非S集中的D[]值，看看是否可通過新加入的w點讓其距離更短：if(D[w]+<w,v> < D[v]) then D[v]=D[w]+<w,v>;
四，跳轉到（二）操作，循環（頂點數－1）次，依次找出所有頂點的最短路徑。
算法了解：
先證明： 下一條最短路徑一定是經過S集中的頂點，或是直接到達出發點的。
也就是說下一條最短路徑一定不經過S集外的頂點。
證明：如下圖，v為出發點，假使w為下一條最短路徑的頂點，則<v,u,w>一定小于<v,k>，否則稱k為下一條最短路徑，而不是w，是以<v,u,w> < <v,k> 則 <v,u,w> < <v,k,w> 是以w一定通過S集中的頂點。
第一條最短路徑當然是直到出發點且最短的那條，是以可以掃描初始化後的D[]直接找出最短那條，然後根據以上證明可得下一條最短路徑一定是通過剛找出的那條的，由于下一條最短路徑一定是通過S集的，所有不用每次都掃描所有的路徑，是以隻用更新有通過剛加入的頂點的路徑D[]值（三操作）。再掃描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有頂點。
弗洛伊德（Floyd）算法：
（算出所有每對頂點間的最短路徑）
算法過程：
一，用D[v][w]記錄每一對頂點的最短距離。
二，依次掃描每一個點，并以其為基點再周遊所有每一對頂點D[][]的值，看看是否可用過該基點讓這對頂點間的距離更小。
算法了解：
最短距離有三種情況：
一，兩點的直達距離最短。（如下圖<v,x>）
二，兩點間隻通過一個中間點而距離最短。（圖<v,u>）
三，兩點間用通過兩各以上的頂點而距離最短。（圖<v,w>）
對于第一種情況：在初始化的時候就已經找出來了且以後也不會更改到。
對于第二種情況：弗洛伊德算法的基本操作就是對于每一對頂點，周遊所有其它頂點，看看可否通過這一個頂點讓這對頂點距離更短，也就是周遊了圖中所有的三角形（算法中對同一個三角形掃描了九次，原則上隻用掃描三次即可，但要加入判斷，效率更低）。
對于第三種情況：如下圖的五邊形，可先找一點（比如x，使<v,u>=2），就變成了四邊形問題，再找一點（比如y,使<u,w>=2），可變成三角形問題了（v,u,w），也就變成第二種情況了，由此對于n邊形也可以一步步轉化成四邊形三角形問題。（這裡面不用擔心哪個點要先找哪個點要後找，因為找了任一個點都可以使其變成（n－1）邊形的問題）。
