前幾天在看Floyd算法的時(shí)候，雖然感覺(jué)程序很簡(jiǎn)單，但是讓你動(dòng)手寫(xiě)那些過(guò)程矩陣的時(shí)候就感覺(jué)不怎么簡(jiǎn)單了，就上網(wǎng)找找看有木有簡(jiǎn)便的計(jì)算方法，搜索之后沒(méi)有發(fā)現(xiàn)有現(xiàn)成的例子，只搜到了兩句“弄兩條線，從左上角挪到右下角”，“十字交叉法，從左上角到右下角”，除此之外就再也木有找到有用的東西了。沒(méi)有內(nèi)容就創(chuàng)造內(nèi)容，填補(bǔ)空白！

先來(lái)簡(jiǎn)單分析下,由于矩陣中對(duì)角線上的元素始終為0,因此以k為中間點(diǎn)時(shí),從上一個(gè)矩陣到下一個(gè)矩陣變化時(shí),矩陣的第k行,第k列和對(duì)角線上的元素是不發(fā)生改變的（對(duì)角線上都是0，因?yàn)橐粋€(gè)頂點(diǎn)到自己的距離就是0，一直不變；而當(dāng)k為中間點(diǎn)時(shí)，k到其他頂點(diǎn)（第k行）和其他頂點(diǎn)到k（第k列）的距離是不變的）。

因此每一步中我們只需要判斷4*4-3*4+2=6個(gè)元素是否發(fā)生改變即可,也就是要判斷既不在第k行第k列又不在對(duì)角線上的元素。具體計(jì)算步驟如下：以k為中間點(diǎn)（1）“三條線”：劃去第k行，第k列，對(duì)角線（2）“十字交叉法”：對(duì)于任一個(gè)不在三條線上的元素x，均可與另外在k行k列上的3個(gè)元素構(gòu)成一個(gè)2階矩陣，x是否發(fā)生改變與2階矩陣中不包含x的那條對(duì)角線上2個(gè)元素的和有關(guān)，若二者之和小于x，則用它們的和替換x，對(duì)應(yīng)的Path矩陣中的與x相對(duì)應(yīng)的位置用k來(lái)替代。。。

下面來(lái)具體看高分筆記上面的那個(gè)題目吧。。。。

詳細(xì)圖解：

經(jīng)過(guò)以上4步就可以得到最終結(jié)果了。。。寫(xiě)的比較繁瑣，但是看明白了之后，計(jì)算將會(huì)非常簡(jiǎn)單啊。。。。。

轉(zhuǎn)載于:https://www.cnblogs.com/Fy1999/p/9531593.html

總結(jié)

以上是生活随笔為你收集整理的Floyd-Warshall算法过程中矩阵计算方法—十字交叉法（转）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。