問：如何計(jì)算出Floyd最短路徑算法中的路徑鏈？

程序猿答疑：

最近看了網(wǎng)上一些Floyd最短路徑算法的實(shí)現(xiàn)，在求出最短路徑的距離矩陣和路徑矩陣后如果需要具體列出某兩點(diǎn)之間的路徑都是用路徑矩陣動(dòng)態(tài)打打印的，沒有保存到具體的數(shù)據(jù)結(jié)構(gòu)中。今天程序員答疑給大家演示下如何用Matlab語言實(shí)現(xiàn)Floyd最短路徑算法并計(jì)算路徑鏈，路徑鏈保存在列表中，在Matlab中的形式為一個(gè)1*n的矩陣。

Floyd算法

如上圖，6個(gè)點(diǎn)A1、A2、A3、A4、A5、A6，點(diǎn)與點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離，如A1到A2的距離為5，點(diǎn)與點(diǎn)之間沒有直接連線表示兩點(diǎn)之間不能直達(dá)，可通過其他點(diǎn)作為中間點(diǎn)形成通路，如A1到A3沒有直達(dá)路徑，但從A1出發(fā)可以先到A2，再從A2到A3，這條路徑的長(zhǎng)度為9（A1到時(shí)A2距離為5，A2到A3距離為4，兩者之和為9）。我們把6個(gè)點(diǎn)每2個(gè)點(diǎn)之間的連線距離填寫在一個(gè)鄰接矩陣a中，矩陣的i行j列上的數(shù)字a[i][j]為A[i]點(diǎn)與A[j]點(diǎn)的直接連線距離。如果兩點(diǎn)之間沒有直接連線，直達(dá)距離為無窮大，用inf表示（inf在Matlab中表示無窮大），同一點(diǎn)與自身的距離為0。上圖中的a矩陣為

為敘述方便，程序員答疑直接用Matlab中的矩陣形式表示矩陣（帶分號(hào)；）。我們可以看到，鄰接矩陣是一個(gè)對(duì)稱矩陣，即第i行第j列上的數(shù)字與第j行第i列的數(shù)字相同，即a[i][j]=a[j][i]，這是因?yàn)锳[i]點(diǎn)與A[j]點(diǎn)的連線距離就是A[j]點(diǎn)與A[i]點(diǎn)的連線距離；同時(shí)可以觀察到鄰接矩陣上的主對(duì)角線上的數(shù)字a[i][i]為0，即A[i]點(diǎn)到A[i]點(diǎn)的距離記為0（在一個(gè)二維的數(shù)字矩陣中,從左上角至右下角的對(duì)角線為主對(duì)角線，從右上角至左下角的對(duì)角線為次對(duì)角線）。

Floyd算法的輸出為最短距離矩陣d和路由矩陣p，最短距離矩陣d的第i行第j列數(shù)值d[i][j]表示A[i]點(diǎn)到A[j]點(diǎn)的最短路徑長(zhǎng)度，路由矩陣p的第i行第j列數(shù)值p[i][j]（假設(shè)為k）表示A[i]點(diǎn)到A[j]點(diǎn)的最短路徑由A[i]點(diǎn)到A[k]點(diǎn)的連線和A[k]點(diǎn)到A[j]點(diǎn)的最短路徑組合而成，如果k=j，A[k]點(diǎn)到A[j]的最短路徑長(zhǎng)度為0。最短距離矩陣d初始設(shè)置為與鄰接矩陣a相同，路由矩陣p初始設(shè)置為每列上的數(shù)值與列序號(hào)相同。兩個(gè)矩陣初始值的含義為兩個(gè)點(diǎn)的最短距離初始化為兩點(diǎn)的直接連線長(zhǎng)度，最短路徑為兩點(diǎn)間的直接連線（若無直接連線仍認(rèn)為距離為無窮大）。比如p[2][3]的值為3，即A2點(diǎn)到A3點(diǎn)的最短路徑由A2點(diǎn)到A3點(diǎn)的連線和A3點(diǎn)到A3點(diǎn)的最短路徑組合而成，A3點(diǎn)到A3點(diǎn)的最短路徑長(zhǎng)度為0，即在初始路由矩陣p中，A2點(diǎn)到A3點(diǎn)的最短路徑為A2到A3的連線，用A2->A3表示，最短路徑長(zhǎng)度為4。當(dāng)然，這和最終結(jié)果可能不同，比如初始路由矩陣p中A1點(diǎn)到A4點(diǎn)的最短路徑為A1->A4，最短路徑長(zhǎng)度為8，而實(shí)際情況是A1點(diǎn)到A4點(diǎn)的最短路徑為A1->A5->A4表示，最短路徑長(zhǎng)度為7。

Floyd算法的思想是對(duì)于任意兩點(diǎn)A[i]和A[j]，如果存在一個(gè)點(diǎn)A[k]使得A[i]和A[k]的最短路徑長(zhǎng)度d[i][k]與A[i]和A[j]的最短路徑長(zhǎng)度d[k][j]之和小于當(dāng)前A[i]和[j]和最短路徑之和d[i][j]，則更新d[i][j]為d[i][k]+d[k][j]，并設(shè)置p[i][j]=p[i][k]，即把路徑A[i]到A[j]的A[i]的下一個(gè)點(diǎn)由p[i][j]換為路徑A[i]到A[k]的A[i]的下一個(gè)點(diǎn)p[i][k]，具體算法如下（Matlab代碼源文件名為floyd.m）：

對(duì)于圖中6個(gè)點(diǎn)的距離數(shù)據(jù)應(yīng)用Floyd算法得到

矩陣d和p是打印在Matlab命令行窗口的形式，與代碼中的矩陣表現(xiàn)形式稍有不同（不帶分號(hào)；）。

路徑鏈

根據(jù)矩陣d和p可以得出圖中任意兩點(diǎn)間的最短路徑和最短路徑的長(zhǎng)度。例如A1到A2的最短路徑長(zhǎng)度為d[1][2]=5，p[1][2]=2，即A1到A2的最短路徑要從A1先到A2，A2已經(jīng)是終點(diǎn)了，不再繼續(xù)查找路徑，最短路徑為A1->A2。又如A2到A6的最短路徑長(zhǎng)度為d[2][6]=11，p[2][6]=1，即A2到A6的最短路徑要從A2先到A1，A2->A1，再看p[1][6]的值為6，A6已經(jīng)是終點(diǎn)了，不再繼續(xù)查找路徑，最短路徑為A1->A2->A6。

上述查找最短路徑的方法包含著遞歸的思想，程序猿答疑用遞歸算法計(jì)算路徑鏈（Matlab代碼源文件名為path.m）。

打印出圖中任意兩點(diǎn)間的最短路徑鏈（Matlab代碼源文件名為main.m）。

代碼輸出結(jié)果為：