建議電腦端觀看

算法名稱? ?? ? ：迪杰斯特拉

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

????????概述：有無(wú)向圖P，起點(diǎn)A，求其它P中所有點(diǎn)到A點(diǎn)得最短路長(zhǎng)度?

算法局限性? ??：負(fù)邊權(quán)無(wú)法使用?

算法涉及思想：貪心，減治?

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

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

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

????????迪杰斯特拉：

????????????????利用有效信息進(jìn)行貪心，可以減少多余的前置運(yùn)算

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

????????對(duì)初始情況，除初始點(diǎn)未知任何最短路徑?

????????????????設(shè)初始點(diǎn)為A

????????????????圖中存在一點(diǎn)B是A的直連點(diǎn)

????????????????命題1：

????????????????????????假設(shè)A->B的長(zhǎng)度小于其它A的直連點(diǎn)到A的長(zhǎng)度

????????????????????????則A->B是A到B的最短路?

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

????????????????????????假設(shè)存在一個(gè)鏈A->N1->N2->...->Nn->B?

????????????????????????????????且這個(gè)鏈?zhǔn)茿到B的最短路

????????????????????????則A->B的長(zhǎng)度<A->N1的長(zhǎng)度

????????????????????????即A->B不是A到B的最短路?

????????????????????????證得：命題1的逆否命題為真，故命題1為真?

????????????????由命題1得：在初始情況下，必然能從與A直接相連的若干個(gè)點(diǎn)中找到一個(gè)

? ?????????????????????????????點(diǎn)，該點(diǎn)與A的直接距離就是其最短路徑

????????對(duì)后續(xù)情況，已知部分最短路徑?

????????????????設(shè)已經(jīng)求出最短路的點(diǎn)集合為S{A,N1,N2,N3,...,Nn}?

????????????????設(shè)A為初始點(diǎn)

????????????????S外有一點(diǎn)B?

????????????????命題2：

????????????????????????假設(shè)L3是A到B的最短路，Nan是路上一點(diǎn)，且Nan在S內(nèi)?

????????????????????????假設(shè)L1是A到Nan的最短路

????????????????????????假設(shè)L2是Nan到B的最短路

????????????????????????則L1+L2=L3?

????????????????證明2：

????????????????????????假設(shè)L4>L1，L4是A到Nan的另一條路?

????????????????????????假設(shè)L5>L2，L5是Nan到B的另一條路?

????????????????則知：

????????????????????????L1+L2<L4+L5?

????????????????????????L1+L2<L1+L5

????????????????????????L1+L2<L4+L2

????????????????由最短路定義得：

????????????????????????L3=L1+L2?

????????????????命題2得證

????????????????由命題2得：需要解決的問(wèn)題從找最短路變成了找Nan

????????????????核心優(yōu)化（減治）：?

????????????????????????如果所有S內(nèi)的點(diǎn)重合在一處，那么就不必找Nan了

????????????????????????????????此時(shí)L1=0，L2即是L3

????????????????????????????????而且A與Nan重合，故L2就是A到B的最短路

????????????????????????????????問(wèn)題甚至轉(zhuǎn)化成了初始情況：

????????????????????????????????????????A與S外的點(diǎn)“直連”（即0+L2）

????????????????????????????????此時(shí)可以用初始情況的結(jié)論來(lái)解決下一個(gè)點(diǎn)?

操作總論：

????????初始情況時(shí)，找到與A直連的最近的點(diǎn)B

????????即求得B的最短路，并將之放入S中?

????????為了保持所有S中的點(diǎn)與A重合在一處，

????????需要將每次放入S的新點(diǎn)N做以下處理：

????????????????1.設(shè)M與N直連，A到M的已知距離是L

????????????????2.將L更新為min（L，A到N的最短路+M到N的距離）?

????????這樣處理之后，N點(diǎn)與A點(diǎn)可重合

????????????????而A與S外點(diǎn)之間的距離又沒(méi)有被這個(gè)操作影響