《計(jì)算機(jī)通信網(wǎng)-》-網(wǎng)絡(luò)層Part2省公開課金獎(jiǎng)全國(guó)賽課一等獎(jiǎng)微課獲獎(jiǎng)?wù)n件

5.3.4幾個(gè)動(dòng)態(tài)路由算法動(dòng)態(tài)路由算法依據(jù)網(wǎng)絡(luò)動(dòng)態(tài)改變計(jì)算路由，形成路由表路由表自動(dòng)形成并依據(jù)拓?fù)涓淖冏詣?dòng)更新適應(yīng)于網(wǎng)拓?fù)涓淖兙W(wǎng)絡(luò)、大網(wǎng)如廣域網(wǎng)、互聯(lián)網(wǎng)包括問題節(jié)點(diǎn)之間交換路由信息快速適應(yīng)拓?fù)涓淖兏兄負(fù)涓淖兛焖賯鬟f改變信息快速形成新穩(wěn)定路由（無(wú)環(huán)路、不震蕩，快速收斂）

★1/405.3.4幾個(gè)動(dòng)態(tài)路由算法中心路由算法逆向?qū)W習(xí)法分布式路由算法（重點(diǎn)）距離矢量法鏈路狀態(tài)法

2/40中心路由算法（集中路由）原理各個(gè)節(jié)點(diǎn)定時(shí)將本節(jié)點(diǎn)信道及相鄰節(jié)點(diǎn)信息匯報(bào)給中心路由計(jì)算機(jī)由中心路由計(jì)算機(jī)計(jì)算出各節(jié)點(diǎn)到其它節(jié)點(diǎn)最正確路由，然后分配到各個(gè)節(jié)點(diǎn)特點(diǎn)理論上講能夠得到全網(wǎng)最優(yōu)路由（因算法考慮了流量、節(jié)點(diǎn)等全網(wǎng)信息）但實(shí)現(xiàn)困難，極難在大網(wǎng)中使用，適應(yīng)于小網(wǎng)，原因有三：信息上傳困難（各節(jié)點(diǎn)定時(shí)上傳信息會(huì)造成中心路由計(jì)算機(jī)附近節(jié)點(diǎn)及線路擁塞）同時(shí)困難（節(jié)點(diǎn)很多，中心反饋新路由時(shí)，各節(jié)點(diǎn)接收時(shí)間不一樣，可能會(huì)造成同一網(wǎng)里有節(jié)點(diǎn)使用新路由，有使用老路由）路由更新過時(shí)（可能會(huì)出現(xiàn)路由更新抵達(dá)時(shí)，節(jié)點(diǎn)情況已變）

21345中心路由計(jì)算機(jī)★3/40逆向（反向）學(xué)習(xí)法原理依據(jù)接收分組中源地址和接收端口號(hào)，形成轉(zhuǎn)發(fā)表，方便下次作為目標(biāo)節(jié)點(diǎn)時(shí)轉(zhuǎn)發(fā)路徑特點(diǎn)能動(dòng)態(tài)適應(yīng)新節(jié)點(diǎn)加入對(duì)線路故障、節(jié)點(diǎn)損壞反應(yīng)遲鈍適應(yīng)拓?fù)浣Y(jié)構(gòu)相對(duì)穩(wěn)定、小網(wǎng)目標(biāo)節(jié)點(diǎn)端口距離………………AnDn

CA收到從A送來(lái)分組路由表中統(tǒng)計(jì)從該接口能夠抵達(dá)A★4/40分布式動(dòng)態(tài)路由算法基本原理節(jié)點(diǎn)之間需相互交換路由信息節(jié)點(diǎn)單獨(dú)計(jì)算路由基本特點(diǎn)局部最優(yōu)，全局不一定最優(yōu)相互交換信息越詳細(xì)、越頻繁，路由優(yōu)化越好，但造成額外開銷也越大。需要在額外開銷和路由更新頻率之間進(jìn)行折中優(yōu)點(diǎn)動(dòng)態(tài)反應(yīng)網(wǎng)絡(luò)改變，路由表自動(dòng)形成與更新（不需人工干預(yù)）局部最優(yōu)，路由開銷少缺點(diǎn)局部最優(yōu)路由，不是全局最優(yōu)路由可能出現(xiàn)不一致（矛盾）路由可能出現(xiàn)路由震蕩（路由表改變太快）可能出現(xiàn)路由發(fā)散（不能收斂）

★5/40分布式路由算法關(guān)鍵點(diǎn)

交換路由信息：分布式計(jì)算：節(jié)點(diǎn)依據(jù)交換路由信息，采取最優(yōu)路由計(jì)算方法計(jì)算最正確路由哪些信息？與誰(shuí)交換？邊交換信息邊計(jì)算可達(dá)、距離、費(fèi)用、負(fù)載、延時(shí)……與鄰居、與全部節(jié)點(diǎn)何時(shí)交換？定時(shí)、拓?fù)涓淖儠r(shí)★6/40兩種經(jīng)典分布式路由算法基于網(wǎng)絡(luò)距離分布式路由算法---矢量距離法基于信道狀態(tài)分布式路由算法---鏈路狀態(tài)法

7/40矢量距離法（V-D：VectorDistance）依據(jù)協(xié)議設(shè)計(jì)者命名，也稱為Bellman-Ford路由算法Ford-Fulkerson路由算法基本思想每個(gè)節(jié)點(diǎn)都保持一張到其它節(jié)點(diǎn)路由表（目標(biāo)節(jié)點(diǎn)，下一節(jié)點(diǎn)，距離）“距離”度量標(biāo)準(zhǔn)能夠是跳數(shù)或時(shí)延等鄰居之間交換路由信息（目標(biāo)節(jié)點(diǎn)，距離）依據(jù)收到相鄰節(jié)點(diǎn)信息，判斷并決定是否更新路由算法包括內(nèi)容初始路由表怎樣建立？鄰居交換哪些信息?怎樣依據(jù)鄰居信息計(jì)算并更新自己路由表？

★8/40矢量距離法算法幾個(gè)步驟初始化建立初始路由表擴(kuò)散向鄰居擴(kuò)散自己路由表信息計(jì)算依據(jù)收到相鄰節(jié)點(diǎn)信息，計(jì)算最短路徑，更新路由表再擴(kuò)散、再計(jì)算這么就逐步形成了全網(wǎng)拓?fù)浣Y(jié)構(gòu)使每個(gè)節(jié)點(diǎn)都計(jì)算出了到其它節(jié)點(diǎn)路徑信息值得注意是：何時(shí)向鄰居擴(kuò)散路由信息？定時(shí)拓?fù)浒l(fā)生改變時(shí)

★9/40距離矢量算法1）初始路由表建立（目標(biāo)節(jié)點(diǎn)，下一節(jié)點(diǎn)，距離）=（V0，G0，D0）2）路由表向鄰居擴(kuò)散

21345611211111146532133311224444655注意：度量值能夠是節(jié)點(diǎn)跳數(shù)、時(shí)延等度量參數(shù)★10/40距離矢量算法各節(jié)點(diǎn)初始路由表：直接相連節(jié)點(diǎn)路由信息

213456111111112目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離111331441目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離442551目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離331441661目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離111221441551目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331551662★11/40距離矢量算法3）節(jié)點(diǎn)計(jì)算并更新本節(jié)點(diǎn)路由表相鄰節(jié)點(diǎn)定時(shí)交換信息（目標(biāo)節(jié)點(diǎn)，距離）=（V，D）當(dāng)某節(jié)點(diǎn)A收到相鄰節(jié)點(diǎn)j信息（Vx，DjX）時(shí)

（Vx表示目標(biāo)地為X節(jié)點(diǎn)，Djx為j到X節(jié)點(diǎn)距離）

A節(jié)點(diǎn)更新情況以下：如A路由表中無(wú)此項(xiàng)，則添加表項(xiàng)（Vx，j，D0+DXj）

（D0為A與鄰居j距離）如A路由表中有Vx項(xiàng)，（Vx，k，DAx）若k≠jDAx>D0+Djx，則表項(xiàng)更新為（Vx，j，D0+DjX

）（新、短路徑）DAx≦D0+Djx，則此表項(xiàng)保持不變?nèi)鬹=j不論DAx大小怎樣，都應(yīng)更新為（Vx，j，D0+DjX）（原路徑可能改變，需更新）

★12/40距離矢量算法

目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331信息公布者2目標(biāo)節(jié)點(diǎn)距離113141節(jié)點(diǎn)1路由表初始值收到節(jié)點(diǎn)3路由信息目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331更新后公布者3目標(biāo)節(jié)點(diǎn)距離11214151收到節(jié)點(diǎn)2路由信息目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422距離更新=到鄰居節(jié)點(diǎn)距離+鄰居節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離更新后213456112111111422532關(guān)13/40距離矢量算法

213456112111111目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532節(jié)點(diǎn)1當(dāng)前路由表節(jié)點(diǎn)1向節(jié)點(diǎn)2公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離21314252節(jié)點(diǎn)1向節(jié)點(diǎn)3公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離21314252關(guān)14/40距離矢量算法

213456112111111目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532節(jié)點(diǎn)1路由表更新距離更新=到鄰居節(jié)點(diǎn)距離+鄰居節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離收到節(jié)點(diǎn)2路由信息公布者2目標(biāo)節(jié)點(diǎn)距離1131415263目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532更新后624公布者3目標(biāo)節(jié)點(diǎn)距離1121415162目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532更新后62433關(guān)15/40距離矢量算法

4）各節(jié)點(diǎn)將更新后路由表分別向自己鄰居擴(kuò)散，然后計(jì)算并再次更新路由表當(dāng)每個(gè)節(jié)點(diǎn)路由表包含了全部其它節(jié)點(diǎn)路由時(shí)，就形成了一個(gè)穩(wěn)定路由，只要拓?fù)洳桓淖?，路由表就保持不變，不然?huì)重新計(jì)算。16/40距離矢量算法相關(guān)問題水平分割節(jié)點(diǎn)沒有必要將從某節(jié)點(diǎn)收到信息再傳回給該節(jié)點(diǎn)無(wú)窮計(jì)數(shù)距離矢量算法會(huì)出現(xiàn)路由環(huán)路設(shè)計(jì)最大路徑長(zhǎng)度（跳數(shù)），以減輕環(huán)路出現(xiàn)時(shí)帶來(lái)?yè)p害用毒性反轉(zhuǎn)方法，破壞路由環(huán)路

17/40水平分割

213456111111111目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532節(jié)點(diǎn)1當(dāng)前路由表節(jié)點(diǎn)1向節(jié)點(diǎn)2公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離21314252節(jié)點(diǎn)1向節(jié)點(diǎn)3公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離21314252節(jié)點(diǎn)沒有必要將從某節(jié)點(diǎn)收到信息再傳回給該節(jié)點(diǎn)18/40無(wú)窮計(jì)數(shù)在某種情況下，距離矢量算法可能出現(xiàn)路由環(huán)路，其現(xiàn)象是路由表項(xiàng)隨路由信息更新，不停增加。

ACBD正常情況：A認(rèn)為到D經(jīng)過BC認(rèn)為到D經(jīng)過BB認(rèn)為到D經(jīng)過D路由環(huán)路：A認(rèn)為到D經(jīng)過BC認(rèn)為到D經(jīng)過AB認(rèn)為到D經(jīng)過C19/40

ACBD平時(shí)：A收到C通知：D有兩跳A收到B通知：D有一跳選BC收到A通知：D有兩跳C收到B通知：D有一跳選B當(dāng)B到D鏈路斷掉后，一個(gè)可能情形：B告訴A、C：D不可達(dá)A重新選路，恰好收到C通知D有兩跳（C還沒收到B更新信息）A選擇到D經(jīng)過C，距離為三跳A通知B：D有三跳B選擇到D經(jīng)過A，距離為四跳C收到B先前D不可達(dá)更新，重新選路B通知C：D有四跳C選擇到D經(jīng)過B，距離為五跳出現(xiàn)路由環(huán)路，并計(jì)數(shù)到無(wú)窮大20/40毒性反轉(zhuǎn)－－處理路由環(huán)路

213456112111111目標(biāo)節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532633節(jié)點(diǎn)1當(dāng)前路由表節(jié)點(diǎn)1向節(jié)點(diǎn)2公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離31425263節(jié)點(diǎn)1向節(jié)點(diǎn)3公布路由信息信息公布者1目標(biāo)節(jié)點(diǎn)距離21425263節(jié)點(diǎn)將從某節(jié)點(diǎn)收到信息再傳回給該節(jié)點(diǎn)時(shí)，告訴對(duì)方不能從我這里過無(wú)窮大無(wú)窮大無(wú)窮大21/40DV協(xié)議其它改進(jìn)觸發(fā)更新收到路由信息有沒有窮大路由項(xiàng)，直接更新對(duì)應(yīng)路由表項(xiàng)更新抑制無(wú)窮大距離路由項(xiàng)保留一段時(shí)間不更新(直到該信息傳遍整個(gè)網(wǎng)絡(luò))22/40距離矢量算法小節(jié)特點(diǎn)：只與鄰節(jié)點(diǎn)交換路由信息各節(jié)點(diǎn)獨(dú)立計(jì)算最優(yōu)路徑（但依賴鄰居計(jì)算結(jié)果）能適應(yīng)網(wǎng)絡(luò)拓?fù)涓淖兎€(wěn)定后，形成最短路徑算法簡(jiǎn)單缺點(diǎn)：網(wǎng)絡(luò)改變擴(kuò)散到全網(wǎng)速度慢擴(kuò)散速度：全部節(jié)點(diǎn)都發(fā)覺改變速度路由收斂慢收斂速度：大家分別計(jì)算，結(jié)果到達(dá)統(tǒng)一速度存在路由環(huán)－－在網(wǎng)絡(luò)改變未擴(kuò)散完全時(shí)。

小網(wǎng)★23/40鏈路狀態(tài)路由（L-S：link-state）定理若節(jié)點(diǎn)掌握了全網(wǎng)全部節(jié)點(diǎn)鏈路情況，節(jié)點(diǎn)就掌握了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)鏈路情況：有幾條鏈路，連接對(duì)端節(jié)點(diǎn)例：節(jié)點(diǎn)R0得到了節(jié)點(diǎn)Rk鏈路情況，R0就可畫出它拓?fù)鋵?duì)端節(jié)點(diǎn)鏈路距離RxdxRydyRzdzRk鏈路情況RkRxRyRzdxdydz若知道Ry鏈路情況，就知道它是否與Rx、Rz相連24/40鏈路狀態(tài)路由關(guān)鍵問題需要在以下情況下與全部節(jié)點(diǎn)交互不知道存在哪些節(jié)點(diǎn)沒有建立路由假如處理了上述問題，每個(gè)節(jié)點(diǎn)都能夠構(gòu)建網(wǎng)絡(luò)拓?fù)湟晥D用拓?fù)湟晥D計(jì)算到各節(jié)點(diǎn)最短路由計(jì)算結(jié)果形成自己轉(zhuǎn)發(fā)表因?yàn)檎莆樟司W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，節(jié)點(diǎn)能夠計(jì)算出最短路由，當(dāng)然也能夠計(jì)算出次短路由，以及更多條路由路由策略：最短路由優(yōu)先SPF，ShortestPathFirst25/40SPF路由功效框圖依據(jù)上述描述，能夠畫出SPF功效框圖SPF路由SPF路由協(xié)議網(wǎng)絡(luò)拓?fù)湟晥D功效當(dāng)?shù)劓溌窢顟B(tài)功效最短路由計(jì)算功效與全部節(jié)點(diǎn)交互與鄰居節(jié)點(diǎn)交互(掌握鏈路狀態(tài))轉(zhuǎn)發(fā)表鏈路增減鏈路通斷狀態(tài)改變…送出自己鏈路狀態(tài)獲取節(jié)點(diǎn)鏈路狀態(tài)數(shù)據(jù)分組轉(zhuǎn)發(fā)26/40鏈路狀態(tài)算法基本思想普通以時(shí)延作為度量參數(shù)發(fā)覺鄰居并測(cè)量與鄰居時(shí)延（延遲，鏈路狀態(tài)）與全部節(jié)點(diǎn)交流與鄰居鏈路狀態(tài)信息獨(dú)立計(jì)算出到其它節(jié)點(diǎn)最正確路徑注意影響時(shí)延可能原因線路速率當(dāng)前負(fù)載節(jié)點(diǎn)處理能力互聯(lián)網(wǎng)中普遍使用OSPF算法采取L-S法

鏈路狀態(tài)：了解為鏈路開銷鏈路質(zhì)量延遲等度量★27/40鏈路狀態(tài)算法算法基本步驟，每個(gè)節(jié)點(diǎn)都進(jìn)行以下工作：發(fā)覺鄰居探尋鄰居，得到鄰居唯一地址測(cè)量鏈路開銷測(cè)量到各鄰居節(jié)點(diǎn)延遲（鏈路質(zhì)量）交換路由信息形成鏈路狀態(tài)分組，向全部節(jié)點(diǎn)擴(kuò)散充實(shí)路由信息庫(kù)依據(jù)收到各節(jié)點(diǎn)鏈路狀態(tài)信息，進(jìn)而得出全網(wǎng)拓?fù)溆?jì)算路由表依據(jù)自己掌握路由信息，獨(dú)立計(jì)算本節(jié)點(diǎn)到其它節(jié)點(diǎn)最正確路由（最小時(shí)延）尤其注意：鏈路狀態(tài)算法交流路由信息：鏈路狀態(tài)信息（本節(jié)點(diǎn)到鄰居延遲）交流對(duì)象：向全部節(jié)點(diǎn)交流方法：擴(kuò)散法路由計(jì)算：只依據(jù)自己掌握路由信息，獨(dú)立計(jì)算最正確路由（不依賴他人計(jì)算）

★28/40鏈路狀態(tài)算法發(fā)覺鄰居節(jié)點(diǎn)初始時(shí)，每個(gè)節(jié)點(diǎn)都向每個(gè)出口（點(diǎn)到點(diǎn)線路）發(fā)送“Hello”分組，通知自己地址收到分組節(jié)點(diǎn)則回應(yīng)一個(gè)分組通知自己地址尤其強(qiáng)調(diào)：每個(gè)節(jié)點(diǎn)地址必須唯一

ABHello，IamAHello，IamB★29/40鏈路狀態(tài)算法測(cè)量鏈路開銷（鏈路延遲）向鄰居發(fā)送“Echo”分組（對(duì)方必須應(yīng)答）對(duì)方發(fā)送應(yīng)答計(jì)算往返延時(shí)除以2，得到時(shí)延（可計(jì)算幾次得平均值）計(jì)算鏈路開銷時(shí)值得討論問題是否考慮負(fù)荷？?jī)煞N觀念考慮負(fù)荷，從進(jìn)入發(fā)送隊(duì)列排隊(duì)開始算忽略負(fù)荷，從發(fā)送開始算正反方向延時(shí)是否一樣？可能不一樣為分析簡(jiǎn)便，通常忽略差異，用平均值

ABT“Echo”“Echo”Response★30/40鏈路狀態(tài)算法經(jīng)過測(cè)試計(jì)算出到鄰居開銷假設(shè)各節(jié)點(diǎn)測(cè)得開銷以下所表示

A節(jié)點(diǎn)B節(jié)點(diǎn)4C3B開銷鄰居6C5D3A開銷鄰居2D6B1E4A開銷鄰居3E2C2F5B開銷鄰居3D2F1C開銷鄰居2E2D開銷鄰居C節(jié)點(diǎn)D節(jié)點(diǎn)F節(jié)點(diǎn)E節(jié)點(diǎn)★31/40鏈路狀態(tài)算法創(chuàng)建鏈路狀態(tài)分組依據(jù)測(cè)得到全部鄰居延時(shí)，形成鏈路狀態(tài)分組鏈路狀態(tài)分組內(nèi)容公布者：公布信息節(jié)點(diǎn)名稱序號(hào)：序號(hào)大小表示信息新舊時(shí)間：一個(gè)分組在網(wǎng)絡(luò)中存活時(shí)間

BACDEF1225624334C3B時(shí)間序號(hào)A公布者6C3A時(shí)間序號(hào)B公布者5D6B4A時(shí)間序號(hào)C公布者2D1E2C5B時(shí)間序號(hào)D公布者3E2F3D1C時(shí)間序號(hào)E公布者2F2E2D時(shí)間序號(hào)F公布者★32/40鏈路狀態(tài)算法公布鏈路狀態(tài)分組公布對(duì)象：全部節(jié)點(diǎn)公布時(shí)間：定時(shí)，鏈路狀態(tài)發(fā)生改變時(shí)公布方法：擴(kuò)散法（洪泛）采取擴(kuò)散法一定能夠抵達(dá)全網(wǎng)各節(jié)點(diǎn)節(jié)點(diǎn)可能收到多個(gè)相同分組可依據(jù)序號(hào)判別，相同序號(hào)則丟棄重復(fù)節(jié)點(diǎn)也可能收到同一個(gè)公布者不一樣序號(hào)分組依據(jù)公布時(shí)間判別，丟棄老，處理新為防止分組可能在網(wǎng)中循環(huán)經(jīng)過時(shí)間（年紀(jì)）字段防止（按時(shí)間遞減，到0時(shí)將被丟棄）各節(jié)點(diǎn)依據(jù)逐步收到鏈路分組，充實(shí)路由信息庫(kù)，逐步“繪出”拓?fù)鋱D

★33/40鏈路狀態(tài)算法計(jì)算到各節(jié)點(diǎn)最正確路由計(jì)算方法：把本節(jié)點(diǎn)作為源節(jié)點(diǎn)，計(jì)算到其它節(jié)點(diǎn)路由采取著名Dijkstra算法（最短路徑算法）計(jì)算依據(jù)只依據(jù)自己掌握路由信息庫(kù)（拓?fù)洌┆?dú)立計(jì)算最正確路由（不依賴他人計(jì)算）

★34/40鏈路狀態(tài)算法怎樣計(jì)算最正確路由最短路徑算法－－Dijkstra算法

A1A2A4A3A526512151）初始化時(shí)，設(shè)A1到其它不直連節(jié)點(diǎn)距離為∞尋找A1到全部節(jié)點(diǎn)最短路徑A2A3A4A5頂點(diǎn)距離路徑2）選擇距離A1最短節(jié)點(diǎn)及其路徑3）觀察經(jīng)過新選擇路徑是否能更短抵達(dá)其它頂點(diǎn)4）已選擇出節(jié)點(diǎn)和最短路徑將不參加下一輪比較5）重復(fù)2-4步，直到不剩有節(jié)點(diǎn)265∞A2A3A4A1A2A3－－3更新A1A2A33A1A2A4－－∞A1A2A5－－4A1A2A3A4－－4更新A1A2A3A44A1A2A3A5－－8A1A2A54A1A2A3A4A5－－∞更新35/40Dijkstra’sAlgorithm

1Initialization:

2N'={u}3forallnodesv4ifvadjacenttou5thenD(v)=c(u,v)6elseD(v)=∞

78Loop

9findwnotinN'suchthatD(w)isaminimum10addwtoN'

11updateD(v)forallvnotinN':12D(v)=min(D(v),D(w)+c(w,v))13/*newcosttoviseitheroldcosttovorknown14sho