最短路f_d

1、路徑優(yōu)化的路徑優(yōu)化的FloyddijkstraA算法的算法的matlab代碼代碼路徑優(yōu)化的FloyddijkstraA算法的matlab代碼附件:Astar.zip附件:dijkstra.zip附件:FloydSPR200711917:41#1會把所有的i到j都處理完后，才會移動到下一個k，這樣就不會有問題了，看來多層循環(huán)的時候，我們一定要當心，否則很容易就弄錯了。接下來就要看一看如何找出最短路徑所行經(jīng)的城市了，這里要用到另一個矩陣P，

2、它的定義是這樣的：p(ij)的值如果為p，就表示i到j的最短行經(jīng)為i...pj，也就是說p是i到j的最短行徑中的j之前的最后一個城市。P矩陣的初值為p(ij)=i。有了這個矩陣之后，要找最短路徑就輕而易舉了。對于i到j而言找出p(ij)，令為p，就知道了路徑i...pj；再去找p(ip)，如果值為q，i到p的最短路徑為i...qp；再去找p(iq)，如果值為r，i到q的最短路徑為i...rq；所以一再反復，到了某個p(it)的值為i時，

3、就表示i到t的最短路徑為it，就會的到答案了，i到j的最短行徑為it...qpj。因為上述的算法是從終點到起點的順序找出來的，所以輸出的時候要把它倒過來。但是，如何動態(tài)的回填P矩陣的值呢？回想一下，當d(ij)d(ik)d(kj)時，就要讓i到j的最短路徑改為走i...k...j這一條路，但是d(kj)的值是已知的，換句話說，就是k...j這條路是已知的，所以k...j這條路上j的上一個城市(即p(kj))也是已知的，當然，因為要改走i

4、...k...j這一條路，j的上一個城市正好是p(kj)。所以一旦發(fā)現(xiàn)d(ij)d(ik)d(kj)，就把p(kj)存入p(ij)。下面是具體的C代碼：#include#include#include#defineMAXSIZE20voidfloyd(int[][MAXSIZE]int[][MAXSIZE]int)voiddisplay_path(int[][MAXSIZE]int[][MAXSIZE]int)voidreverse(i