偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

坐在馬桶上看算法：只有五行的Floyd最短路算法

作者：ahalei
開發(fā) 后端 前端 算法
此算法由Robert W. Floyd（羅伯特·弗洛伊德）于1962年發(fā)表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍爾）也獨(dú)立發(fā)表了這個(gè)算法。Robert W．Floyd這個(gè)牛人是朵奇葩，他原本在芝加哥大學(xué)讀的文學(xué)，但是因?yàn)楫?dāng)時(shí)美國(guó)經(jīng)濟(jì)不太景氣，找工作比較困難，無奈之下到西屋電氣公司當(dāng)了一名計(jì)算機(jī)操作員，在IBM650機(jī)房值夜班，并由此開始了他的計(jì)算機(jī)生涯。

[[110550]]

暑假，小哼準(zhǔn)備去一些城市旅游。有些城市之間有公路，有些城市之間則沒有，如下圖。為了節(jié)省經(jīng)費(fèi)以及方便計(jì)劃旅程，小哼希望在出發(fā)之前知道任意兩個(gè)城市之前的最短路程。

081028xjgvimgz7882qdu7.png

上圖中有4個(gè)城市8條公路，公路上的數(shù)字表示這條公路的長(zhǎng)短。請(qǐng)注意這些公路是單向的。我們現(xiàn)在需要求任意兩個(gè)城市之間的最短路程，也就是求任意兩個(gè)點(diǎn)之間的最短路徑。這個(gè)問題這也被稱為“多源最短路徑”問題。

現(xiàn)在需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)圖的信息，我們?nèi)匀豢梢杂靡粋€(gè)4*4的矩陣（二維數(shù)組e）來存儲(chǔ)。比如1號(hào)城市到2號(hào)城市的路程為2，則設(shè)e[1][2]的值為2。2號(hào)城市無法到達(dá)4號(hào)城市，則設(shè)置e[2][4]的值為∞。另外此處約定一個(gè)城市自己是到自己的也是0，例如e[1][1]為0，具體如下。

081028o2n5ebn8hdeh9e5l.png

現(xiàn)在回到問題：如何求任意兩點(diǎn)之間最短路徑呢？通過之前的學(xué)習(xí)我們知道通過深度或廣度優(yōu)先搜索可以求出兩點(diǎn)之間的最短路徑。所以進(jìn)行n2遍深度或廣度優(yōu)先搜索，即對(duì)每?jī)蓚€(gè)點(diǎn)都進(jìn)行一次深度或廣度優(yōu)先搜索，便可以求得任意兩點(diǎn)之間的最短路徑?？墒沁€有沒有別的方法呢？

我們來想一想，根據(jù)我們以往的經(jīng)驗(yàn)，如果要讓任意兩點(diǎn)（例如從頂點(diǎn)a點(diǎn)到頂點(diǎn)b）之間的路程變短，只能引入第三個(gè)點(diǎn)（頂點(diǎn)k），并通過這個(gè)頂點(diǎn)k中轉(zhuǎn)即a->k->b，才可能縮短原來從頂點(diǎn)a點(diǎn)到頂點(diǎn)b的路程。那么這個(gè)中轉(zhuǎn)的頂點(diǎn)k是1~n中的哪個(gè)點(diǎn)呢？甚至有時(shí)候不只通過一個(gè)點(diǎn)，而是經(jīng)過兩個(gè)點(diǎn)或者更多點(diǎn)中轉(zhuǎn)會(huì)更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上圖中從4號(hào)城市到3號(hào)城市（4->3）的路程e[4][3]原本是12。如果只通過1號(hào)城市中轉(zhuǎn)（4->1->3），路程將縮短為11（e[4][1]+e[1][3]=5+6=11）。其實(shí)1號(hào)城市到3號(hào)城市也可以通過2號(hào)城市中轉(zhuǎn)，使得1號(hào)到3號(hào)城市的路程縮短為5（e[1][2]+e[2][3]=2+3=5）。所以如果同時(shí)經(jīng)過1號(hào)和2號(hào)兩個(gè)城市中轉(zhuǎn)的話，從4號(hào)城市到3號(hào)城市的路程會(huì)進(jìn)一步縮短為10。通過這個(gè)的例子，我們發(fā)現(xiàn)每個(gè)頂點(diǎn)都有可能使得另外兩個(gè)頂點(diǎn)之間的路程變短。好，下面我們將這個(gè)問題一般化。

當(dāng)任意兩點(diǎn)之間不允許經(jīng)過第三個(gè)點(diǎn)時(shí)，這些城市之間最短路程就是初始路程，如下。

081029zdxxq919ttqt8tu8.png

如現(xiàn)在只允許經(jīng)過1號(hào)頂點(diǎn)，求任意兩點(diǎn)之間的最短路程，應(yīng)該如何求呢？只需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)之間的路程。e[i][1]+e[1][j]表示的是從i號(hào)頂點(diǎn)先到1號(hào)頂點(diǎn)，再?gòu)?號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的路程之和。其中i是1~n循環(huán)，j也是1~n循環(huán)，代碼實(shí)現(xiàn)如下。

  1. for(i=1;i<=n;i++)   
  2. {   
  3.     for(j=1;j<=n;j++)   
  4.     {   
  5.  if ( e[i][j] > e[i][1]+e[1][j] )   
  6. e[i][j] = e[i][1]+e[1][j];   
  7.     }   
  8. } 

在只允許經(jīng)過1號(hào)頂點(diǎn)的情況下，任意兩點(diǎn)之間的最短路程更新為：

081029itl7z7m4l9qqg56d.png

通過上圖我們發(fā)現(xiàn)：在只通過1號(hào)頂點(diǎn)中轉(zhuǎn)的情況下，3號(hào)頂點(diǎn)到2號(hào)頂點(diǎn)（e[3][2]）、4號(hào)頂點(diǎn)到2號(hào)頂點(diǎn)（e[4][2]）以及4號(hào)頂點(diǎn)到3號(hào)頂點(diǎn)（e[4][3]）的路程都變短了。

接下來繼續(xù)求在只允許經(jīng)過1和2號(hào)兩個(gè)頂點(diǎn)的情況下任意兩點(diǎn)之間的最短路程。如何做呢？我們需要在只允許經(jīng)過1號(hào)頂點(diǎn)時(shí)任意兩點(diǎn)的最短路程的結(jié)果下，再判斷如果經(jīng)過2號(hào)頂點(diǎn)是否可以使得i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)之間的路程變得更短。即判斷e[i][2]+e[2][j]是否比e[i][j]要小，代碼實(shí)現(xiàn)為如下。

  1. //經(jīng)過1號(hào)頂點(diǎn)   
  2. for(i=1;i<=n;i++)   
  3.     for(j=1;j<=n;j++)   
  4.  if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];   
  5. //經(jīng)過2號(hào)頂點(diǎn)   
  6. for(i=1;i<=n;i++)   
  7.     for(j=1;j<=n;j++)   
  8.  if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j]; 

在只允許經(jīng)過1和2號(hào)頂點(diǎn)的情況下，任意兩點(diǎn)之間的最短路程更新為：

081029e7gjlaaul4zk7z4n.png

通過上圖得知，在相比只允許通過1號(hào)頂點(diǎn)進(jìn)行中轉(zhuǎn)的情況下，這里允許通過1和2號(hào)頂點(diǎn)進(jìn)行中轉(zhuǎn)，使得e[1][3]和e[4][3]的路程變得更短了。

同理，繼續(xù)在只允許經(jīng)過1、2和3號(hào)頂點(diǎn)進(jìn)行中轉(zhuǎn)的情況下，求任意兩點(diǎn)之間的最短路程。任意兩點(diǎn)之間的最短路程更新為：

081029pd747o8o87o07o7l.png

***允許通過所有頂點(diǎn)作為中轉(zhuǎn)，任意兩點(diǎn)之間最終的最短路程為：

081030h7tmht7cs2h7qftu.png

整個(gè)算法過程雖然說起來很麻煩，但是代碼實(shí)現(xiàn)卻非常簡(jiǎn)單，核心代碼只有五行：

  1. for(k=1;k<=n;k++)   
  2.     for(i=1;i<=n;i++)   
  3.  for(j=1;j<=n;j++)   
  4.      if(e[i][j]>e[i][k]+e[k][j])   
  5.    e[i][j]=e[i][k]+e[k][j]; 

這段代碼的基本思想就是：最開始只允許經(jīng)過1號(hào)頂點(diǎn)進(jìn)行中轉(zhuǎn)，接下來只允許經(jīng)過1和2號(hào)頂點(diǎn)進(jìn)行中轉(zhuǎn)……允許經(jīng)過1~n號(hào)所有頂點(diǎn)進(jìn)行中轉(zhuǎn)，求任意兩點(diǎn)之間的最短路程。用一句話概括就是：從i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)只經(jīng)過前k號(hào)點(diǎn)的最短路程。其實(shí)這是一種“動(dòng)態(tài)規(guī)劃”的思想，關(guān)于這個(gè)思想我們將在《啊哈！算法2——偉大思維閃耀時(shí)》在做詳細(xì)的討論。下面給出這個(gè)算法的完整代碼：

  1. #include <stdio.h>   
  2. int main()   
  3. {   
  4.     int e[10][10],k,i,j,n,m,t1,t2,t3;   
  5.     int inf=99999999; //用inf(infinity的縮寫)存儲(chǔ)一個(gè)我們認(rèn)為的正無窮值   
  6.     //讀入n和m，n表示頂點(diǎn)個(gè)數(shù)，m表示邊的條數(shù)   
  7.     scanf("%d %d",&n,&m);   
  8.   
  9.     //初始化   
  10.     for(i=1;i<=n;i++)   
  11.  for(j=1;j<=n;j++)   
  12.      if(i==j) e[i][j]=0;   
  13. else e[i][j]=inf;   
  14.     //讀入邊   
  15.     for(i=1;i<=m;i++)   
  16.     {   
  17.  scanf("%d %d %d",&t1,&t2,&t3);   
  18.  e[t1][t2]=t3;   
  19.     }   
  20.   
  21.     //Floyd-Warshall算法核心語句   
  22.     for(k=1;k<=n;k++)   
  23.  for(i=1;i<=n;i++)   
  24.      for(j=1;j<=n;j++)   
  25.   if(e[i][j]>e[i][k]+e[k][j] )   
  26.       e[i][j]=e[i][k]+e[k][j];   
  27.   
  28.     //輸出最終的結(jié)果   
  29.     for(i=1;i<=n;i++)   
  30.     {   
  31.      for(j=1;j<=n;j++)   
  32.  {   
  33.      printf("%10d",e[i][j]);   
  34.  }   
  35.  printf("\n");   
  36.     }   
  37.   
  38.     return 0;   
  39. } 

有一點(diǎn)需要注意的是：如何表示正無窮。我們通常將正無窮定義為99999999，因?yàn)檫@樣即使兩個(gè)正無窮相加，其和仍然不超過int類型的范圍（C語言int類型可以存儲(chǔ)的***正整數(shù)是2147483647）。在實(shí)際應(yīng)用中***估計(jì)一下最短路徑的上限，只需要設(shè)置比它大一點(diǎn)既可以。例如有100條邊，每條邊不超過100的話，只需將正無窮設(shè)置為10001即可。如果你認(rèn)為正無窮和其它值相加得到一個(gè)大于正無窮的數(shù)是不被允許的話，我們只需在比較的時(shí)候加兩個(gè)判斷條件就可以了，請(qǐng)注意下面代碼中帶有下劃線的語句。

  1. //Floyd-Warshall算法核心語句   
  2. for(k=1;k<=n;k++)   
  3.   for(i=1;i<=n;i++)   
  4.       for(j=1;j<=n;j++)   
  5.  if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])   
  6.      e[i][j]=e[i][k]+e[k][j]; 

上面代碼的輸入數(shù)據(jù)樣式為：

  1. 4 8   
  2. 1 2 2   
  3. 1 3 6   
  4. 1 4 4   
  5. 2 3 3   
  6. 3 1 7   
  7. 3 4 1   
  8. 4 1 5   
  9. 4 3 12 

***行兩個(gè)數(shù)為n和m，n表示頂點(diǎn)個(gè)數(shù)，m表示邊的條數(shù)。

接下來m行，每一行有三個(gè)數(shù)t1、t2 和t3，表示頂點(diǎn)t1到頂點(diǎn)t2的路程是t3。

得到最終結(jié)果如下：

081030is22w3mmnz3r33m3.png

通過這種方法我們可以求出任意兩個(gè)點(diǎn)之間最短路徑。它的時(shí)間復(fù)雜度是O(N3)。令人很震撼的是它竟然只有五行代碼，實(shí)現(xiàn)起來非常容易。正是因?yàn)樗鼘?shí)現(xiàn)起來非常容易，如果時(shí)間復(fù)雜度要求不高，使用Floyd-Warshall來求指定兩點(diǎn)之間的最短路或者指定一個(gè)點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑也是可行的。當(dāng)然也有更快的算法，請(qǐng)看下一節(jié)：Dijkstra算法。

另外需要注意的是：Floyd-Warshall算法不能解決帶有“負(fù)權(quán)回路”（或者叫“負(fù)權(quán)環(huán)”）的圖，因?yàn)閹в?ldquo;負(fù)權(quán)回路”的圖沒有最短路。例如下面這個(gè)圖就不存在1號(hào)頂點(diǎn)到3號(hào)頂點(diǎn)的最短路徑。因?yàn)?->2->3->1->2->3->…->1->2->3這樣路徑中，每繞一次1->-2>3這樣的環(huán)，最短路就會(huì)減少1，永遠(yuǎn)找不到最短路。其實(shí)如果一個(gè)圖中帶有“負(fù)權(quán)回路”那么這個(gè)圖則沒有最短路。

081030elthvel6et6k886y.png

此算法由Robert W. Floyd（羅伯特·弗洛伊德）于1962年發(fā)表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍爾）也獨(dú)立發(fā)表了這個(gè)算法。Robert W．Floyd這個(gè)牛人是朵奇葩，他原本在芝加哥大學(xué)讀的文學(xué)，但是因?yàn)楫?dāng)時(shí)美國(guó)經(jīng)濟(jì)不太景氣，找工作比較困難，無奈之下到西屋電氣公司當(dāng)了一名計(jì)算機(jī)操作員，在IBM650機(jī)房值夜班，并由此開始了他的計(jì)算機(jī)生涯。此外他還和J.W.J. Williams（威廉姆斯）于1964年共同發(fā)明了著名的堆排序算法HEAPSORT。堆排序算法我們將在第七章學(xué)習(xí)。Robert W．Floyd在1987年獲得了圖靈獎(jiǎng)。

博客地址：http://ahalei.blog.51cto.com/4767671/1383613

責(zé)任編輯：林師授 來源： 51CTO博客
算法Floyd最短算法
相關(guān)推薦

2014-03-03 16:44:57

算法

2014-04-08 15:52:03

算法碼農(nóng)

2011-05-17 13:58:37

最短路徑

2021-03-10 09:50:15

算法Dijkstra短路問題

2021-08-26 17:36:42

Floyd算法數(shù)據(jù)結(jié)構(gòu)

2013-04-23 09:31:52

SQL Server

2023-07-03 07:51:47

2011-12-19 12:39:37

Java

2021-05-10 08:07:40

圖算法路徑頂點(diǎn)

2022-05-11 07:41:31

Python驗(yàn)證碼

2010-04-19 11:21:32

天御五行可信行為管理

2011-04-11 16:32:28

路徑C++

2024-04-02 11:37:59

AGI網(wǎng)絡(luò)模型GAN

2025-08-11 09:14:00

2011-05-17 14:29:29

Dijkstra

2011-05-17 14:11:06

Dijkstra

2020-06-28 07:30:00

推薦算法推薦系統(tǒng)

2013-12-12 10:27:35

通信網(wǎng)絡(luò)OSPF優(yōu)化

2010-04-28 14:30:18

云計(jì)算

2024-05-24 08:00:00

點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)