?? 路徑優化的floyd等算法的matlab代碼.txt
字號:
路徑優化的Floyd,dijkstra,A*算法的matlab代碼
Floyd最短路徑算法
2006-10-20, by leon_jlu
在圖論中經常會遇到這樣的問題，在一個有向圖里，求出任意兩個節點之間的最短距離。我們在離散數學、數據結構課上都遇到過這個問題，在計算機網絡里介紹網絡層的時候好像也遇到過這個問題，記不請了... 但是書本上一律采取的是Dijkstra算法，通過Dijkstra算法可以求出單源最短路徑，然后逐個節點利用Dijkstra算法就可以了。不過在這里想換換口味，采取Robert Floyd提出的算法來解決這個問題。下面讓我們先把問題稍微的形式化一下：
如果有一個矩陣D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距離。若i與j之間無路可通，那么d(ij)就是無窮大。又有d(ii)=0。編寫一個程序，通過這個距離矩陣D，把任意兩個城市之間的最短與其行徑的路徑找出來。
我們可以將問題分解，先找出最短的距離，然后在考慮如何找出對應的行進路線。如何找出最短路徑呢，這里還是用到動態規劃的知識，對于任何一個城市而言，i到j的最短距離不外乎存在經過i與j之間的k和不經過k兩種可能，所以可以令k=1，2，3，...，n(n是城市的數目)，在檢查d(ij)與d(ik)+d(kj)的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j的最短距離，因此d(ik)+d(kj)就是i到j經過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發經過k再到j的距離要比原來的i到j距離短，自然把i到j的d(ij)重寫為d(ik)+d(kj)，每當一個k查完了，d(ij)就是目前的i到j的最短距離。重復這一過程，最后當查完所有的k時，d(ij)里面存放的就是i到j之間的最短距離了。所以我們就可以用三個for循環把問題搞定了，但是有一個問題需要注意，那就是for循環的嵌套的順序：我們可能隨手就會寫出這樣的程序，但是仔細考慮的話，會發現是有問題的。
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
問題出在我們太早的把i-k-j的距離確定下來了，假設一旦找到了i-p-j最短的距離后，i到j就相當處理完了，以后不會在改變了，一旦以后有使i到j的更短的距離時也不能再去更新了，所以結果一定是不對的。所以應當象下面一樣來寫程序：
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
這樣作的意義在于固定了k，把所有i到j而經過k的距離找出來，然后象開頭所提到的那樣進行比較和重寫，因為k是在最外層的，所以會把所有的i到j都處理完后，才會移動到下一個k，這樣就不會有問題了，看來多層循環的時候，我們一定要當心，否則很容易就弄錯了。
接下來就要看一看如何找出最短路徑所行經的城市了，這里要用到另一個矩陣P，它的定義是這樣的：p(ij)的值如果為p，就表示i到j的最短行經為i->...->p->j，也就是說p是i到j的最短行徑中的j之前的最后一個城市。P矩陣的初值為p(ij)=i。有了這個矩陣之后，要找最短路徑就輕而易舉了。對于i到j而言找出p(ij)，令為p，就知道了路徑i->...->p->j；再去找p(ip)，如果值為q，i到p的最短路徑為i->...->q->p；再去找p(iq)，如果值為r，i到q的最短路徑為i->...->r->q；所以一再反復，到了某個p(it)的值為i時，就表示i到t的最短路徑為i->t，就會的到答案了，i到j的最短行徑為i->t->...->q->p->j。因為上述的算法是從終點到起點的順序找出來的，所以輸出的時候要把它倒過來。
但是，如何動態的回填P矩陣的值呢？回想一下，當d(ij)>d(ik)+d(kj)時，就要讓i到j的最短路徑改為走i->...->k->...->j這一條路，但是d(kj)的值是已知的，換句話說，就是k->...->j這條路是已知的，所以k->...->j這條路上j的上一個城市(即p(kj))也是已知的，當然，因為要改走i->...->k->...->j這一條路，j的上一個城市正好是p(kj)。所以一旦發現d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)。
下面是具體的C代碼：
#include
#include
#include
#define MAXSIZE 20
void floyd(int [][MAXSIZE], int [][MAXSIZE], int);
void display_path(int [][MAXSIZE], int [][MAXSIZE], int);
void reverse(int [], int);
void readin(int [][MAXSIZE], int *);
#define MAXSUM(a, b) (((a) != INT_MAX && (b) != INT_MAX) ? \
((a) + (b)) : INT_MAX)
void floyd(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
{
int i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
path[j] = i;
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (dist[j] > MAXSUM(dist[k], dist[k][j]))
{
path[j] = path[k][j];
dist[j] = MAXSUM(dist[k], dist[k][j]);
}
}
void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
{
int *chain;
int count;
int i, j, k;
printf("\n\nOrigin->Dest Dist ath");
printf( "\n-----------------------------");
chain = (int *) malloc(sizeof(int)*n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (i != j)
{
printf("\n%6d->%d ", i+1, j+1);
if (dist[j] == INT_MAX)
printf(" NA ");
else
{
printf("%4d ", dist[j]);
count = 0;
k = j;
do
{
k = chain[count++] = path[k];
} while (i != k);
reverse(chain, count);
printf("%d", chain[0]+1);
for (k = 1; k < count; k++)
printf("->%d", chain[k]+1);
printf("->%d", j+1);
}
}
}
free(chain);
}
#define SWAP(a, b) { temp = a; a = b; b = temp; }
void reverse(int x[], int n)
{
int i, j, temp;
for (i = 0, j = n-1; i < j; i++, j--)
SWAP(x, x[j]);
}
void readin(int dist[][MAXSIZE], int *number)
{
int origin, dest, length, n;
int i, j;
char line[100];
gets(line);
sscanf(line, "%d", &n);
*number = n;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
dist[j] = INT_MAX;
dist = 0;
}
gets(line);
sscanf(line, "%d%d%d", &origin, &dest, &length);
while (origin != 0 && dest != 0 && length != 0)
{
dist[origin-1][dest-1] = length;
gets(line);
sscanf(line, "%d%d%d", &origin, &dest, &length);
}
}
測試程序如下所示：
int main(void)
{
int dist[MAXSIZE][MAXSIZE];
int path[MAXSIZE][MAXSIZE];
int n;
printf("\nInput the path information:");
printf("\n----------------------------\n");
readin(dist, &n);
floyd(dist, path, n);
display_path(dist, path, n);
getchar();
}
其中readin函數規定了輸入的格式，第一列是指出有多少個城市；第二列以后每行三個數；第一個和第二個是一條路徑的起點和終點，第三個數是路徑的長度，最后以三個0作為輸入結束條件。下面是一個輸入的例子：
Input the path information:
--------------------------------------
4
1 2 5
2 1 50
2 3 15
2 4 5
3 1 30
3 4 15
4 1 15
4 3 5
0 0 0
對應的輸出結果為：
Origin->Dest Dist Path
----------------------------------------------
1->2 5 1->2
1->3 15 1->2->4->3
1->4 10 1->2->4
2->1 20 2->4->1
2->3 10 2->4->3
2->4 5 2->4
3->1 30 3->1
3->2 35 3->1->2
3->4 15 3->4
4->1 15 4->1
4->2 20 4->1->2
4->3 5 4->3
Dijkstra算法是由荷蘭計算機科學家艾茲格?迪科斯徹發現的。算法解決的是有向圖中最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 Dijkstra算法可以用來找到兩個城市之間的最短路徑。
Dijkstra算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t，Dijkstra算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。
算法描述
這個算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0）， 同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對于V中所有頂點v除s外d[v]= ∞）。當算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那么從s到u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路徑。這條路徑的長度是d+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個算法經過組織因而當d達到它最終的值的時候沒條邊(u,v)都只被拓展一次。
算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而后每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d值的頂點。當一個頂點u從Q中轉移到了S中，算法對每條外接邊(u,v)進行拓展。
在下面的算法中,u:=Extract_Min(Q)在在頂點集Q中搜索有最小的d值的頂點u。這個頂點被從集合Q中刪除并返回給用戶。
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 初始化
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijstra算法主體
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d + w(u,v) // 拓展邊(u,v)
13 d[v] := d + w(u,v)
14 previous[v] := u
如果我們只對在s和t之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足u=t的話終止程序。
現在我們可以通過迭代來回溯出s到t的最短路徑
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous
現在序列S就是從s到t的最短路徑的頂點集.
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -