建議電腦端觀看

算法名稱(chēng)?? ?? ?：弗洛伊德

算法適用范圍：解決圖論中的多源最短路徑問(wèn)題

????????概述：有無(wú)向圖P，求任意兩點(diǎn)之間的最短路

算法局限性???：無(wú)

算法涉及思想：暴力，枚舉

算法優(yōu)越性?? ?：相對(duì)暴力（深搜）

????????暴力做法：

????????????????遍歷每個(gè)點(diǎn)，以遍歷到的點(diǎn)為起點(diǎn)

????????????????對(duì)整個(gè)圖進(jìn)行一次深搜，得到答案

? ? ? ? 弗洛伊德：

????????????????遍歷每個(gè)點(diǎn)，以遍歷到的點(diǎn)為中間點(diǎn)，

????????????????枚舉兩側(cè)的起點(diǎn)和終點(diǎn)，對(duì)兩條邊進(jìn)行松弛操作

????????????????減少了中間點(diǎn)被重復(fù)計(jì)算的情況?

算法優(yōu)越解釋：

????????命題1：有鏈A->N1->N2->...->Nn->B

????????????????該鏈?zhǔn)茿到B的最短路

????????????????該鏈的任意松弛順序不影響結(jié)果?

????????證明1：

????????????????知：

????????????????????????假定有一點(diǎn)Nan是鏈上的點(diǎn)

????????????????????????則有鏈N(an-1)->Nan->N(an+1)

????????????????????????該鏈長(zhǎng)度為N(an-1)->Nan + Nan->N(an+1)?

????????????????故：

????????????????????????對(duì)于整個(gè)鏈

????????????????????????鏈長(zhǎng)為A->N1 + N1->N2 + N2->N3 + ..... + Nn->B?

????????????????????????每次選取點(diǎn)即在上式中任意挑選相鄰兩項(xiàng)相加?

????????????????????????由加法結(jié)合律知：總值不變

????????????????命題1 得證?

????????由命題1知：

????????????????如下的操作可求出正確答案：

????????????????????????對(duì)任意兩點(diǎn)Ai到Bi的最短路

????????????????????????枚舉每一個(gè)點(diǎn)，將其任意兩個(gè)直連點(diǎn)進(jìn)行松弛

????????????????????????則必然包括最短路鏈上的點(diǎn)，和以該點(diǎn)為中間點(diǎn)的兩個(gè)鏈上直連點(diǎn)

????????????????????????多次之后

????????????????????????即可求出任意兩點(diǎn)之間的最短路

????????核心優(yōu)化分析：

????????????????對(duì)上述操作，任意一個(gè)僅含有三個(gè)點(diǎn)的鏈，都只被枚舉了一次

????????????????大大減小了時(shí)間復(fù)雜度（雖然還是很大）