【正文】 vn。())。Floyd sAlogrithm（ Digraph constamp。 vn。 int const d=weight。 assoc=dynamic_castAssocamp。所以，利用此方法求第 k次的最短邊 共需比較 2（ nk） 1次，即時(shí)間復(fù)雜性為 O（ nk）。 Setamp。 } delete amp。 result=*new GraphAsLists(n)。++v) (*new WeightedVertex(v,*new int(table[v].distance)))。(())。 While(!()) { Assocamp。 Class Assoc:public Association { int priority。 表 算法運(yùn)行過程 頂點(diǎn) 遍數(shù) 初值 1 2 3 4 5 6 a ∞ 3b √ 3b √ 3b √ 3b √ 3b √ 3b b 0 √ 0 √ 0 √ 0 √ 0 √ 0 √ 0 c ∞ 5b 4a √ 4a √ 4a √ 4a √ 4a d ∞ ∞ ∞ 6c √ 6c √ 6c √ 6c e ∞ ∞ ∞ 8c 8c √ 8c √ 8c f ∞ ∞ ∞ ∞ 11d 9e √ 9e 圖 有向圖 最初，除頂點(diǎn) b 的初值為 0 之外，其余各定點(diǎn)的最短路徑長(zhǎng)度估計(jì)值均賦初值為∞，因此在第一遍中可選頂點(diǎn) b。 Dijkstra 算法的本質(zhì)是能夠確定路徑的順序。在這期間，會(huì)有這樣或那樣的軟硬件錯(cuò)誤，主機(jī)、路由器和線路將增加或撤除，拓?fù)浣Y(jié)構(gòu)要多次改變，路由選擇算法必須能妥善處理拓?fù)浣Y(jié)構(gòu)和通信量的變化，而不會(huì)使所有主機(jī)中 的作業(yè)部終止，也不必每當(dāng)某些路由器崩潰時(shí)，都要更新啟動(dòng)該網(wǎng)絡(luò)。 （ routing delay） 路由選擇延遲至的是通過互聯(lián)網(wǎng)絡(luò)從源節(jié)點(diǎn)法搜是發(fā)送數(shù)據(jù)包到目的節(jié)點(diǎn) 所需的時(shí)間，延遲時(shí)間取決于諸多因素，其中包括網(wǎng)絡(luò)鏈路的貸款及網(wǎng)絡(luò)堵塞成都‘沿途每個(gè)路由器端口的隊(duì)列和傳輸?shù)奈锢砭嚯x等。而距離向量路由算法 (也稱作貝爾曼一福特算法 )要求每個(gè)路由器將路由表的全部或部分傳送到與其相鄰的路由器中。在分層路由選擇算法中，任一域中只有一部分路由器可以與其他域中的路由器通信，而其他路由器只能與該域中的路由器通信。例如假設(shè)某一網(wǎng)段失靈了，路由選擇算法在意識(shí)到在個(gè)問題后，應(yīng)盡快為所有路由選擇最佳路徑，避免使用那段網(wǎng)絡(luò)。換句話說，路由選擇算法必須用最低的軟 /硬件開銷來提供最有效的功能。這一區(qū)別決定了路由和交換在移動(dòng)信息的過程中需要使用不同的控制信息，所以兩者實(shí)現(xiàn)各自功能的方式是不同的。一般在路由過程中，信息會(huì)進(jìn)過一個(gè)貨多個(gè)中間節(jié)點(diǎn)。因此，路由選擇協(xié)議必須嚴(yán)格定義其計(jì)算方法。但如果路由器 2還未被更新，它認(rèn)為最優(yōu)路由的下一個(gè)節(jié)點(diǎn)是路由器 2又把數(shù)據(jù)包發(fā)送回路由器 ，數(shù)據(jù)包持續(xù)在這兩個(gè)路由器之間來回傳送，直到路由器 2收到路由修正命令或者達(dá)到數(shù)據(jù)包允許轉(zhuǎn)發(fā)的最大的次數(shù)為止。在平面路由選擇算法中，所有路由器是對(duì)等的，而在分層路由選擇算法中，路由器被劃分成主干路由器和非主干 路由器。這兩種算法在本質(zhì)上存在不同。通常由網(wǎng)絡(luò)管理員給網(wǎng)絡(luò)連累分配可靠性等級(jí)。對(duì)于這些公司來說他們寧可將數(shù)據(jù)包在自己的鏈路上進(jìn)行傳輸（即使這樣可能增加鏈路延遲）也不愿意花錢（省時(shí)間）在公用鏈路上傳輸。作為一種折衷的辦法，許多網(wǎng)絡(luò)試圖使分組必須經(jīng)過的站點(diǎn)減至最少。 在 每次執(zhí)行過程中，只有一個(gè)頂點(diǎn)的 kv 設(shè)置為 true。 int distance。 table[s].distance=0。 v1=()。 result=*new DigraphAsLists(n)。KruskalsAlgorithm(Graph constamp。(())。 Vertex::Number const v1=()。 Prim 算法的關(guān)鍵之處是：每次如何從生成樹 T中道 T 外的所有邊中，找出一條最短邊。 (*new Assoc(0,const_castVertexamp。 intamp。 Graphamp。 圖 1113 Floyd 算法實(shí)現(xiàn) 函數(shù) FloudsAlgorithm 的參數(shù)只想帶全有向圖的 const 的引用，且權(quán)是 int 類的實(shí)例。(*p)。 } Digraphamp。vn。 } delete amp。 Array2Dunsigned intdistance(n,n)。 vn。table[v1].distanced) { table[v1].distance=d。 v0=dynamic_castVertexamp。第二個(gè)參數(shù)也是 const 類型引用， 是一個(gè)指向起始點(diǎn)（頂點(diǎn)）引用。 (*new Edge(result[v0]， result[v1]))。 partition=*new PartitionAsForest(n)。 ++v) (*new Vertex(v))。 ++v) if(v!=s) (*new Edege(result[v],result[table[v],predecessor]))。 table[v1].predecessor=v0。 Vertexamp。 } }。頂點(diǎn) a 的新長(zhǎng)度為 3，頂點(diǎn) c 的新長(zhǎng)度為 5。 （ 1） Kv 是一個(gè)布爾值型的標(biāo)記，它標(biāo)明到定點(diǎn) V 的最短路徑已經(jīng)知道。斷定在 A和 A39。帶寬（ bandwidth）是指鏈路傳輸信息流的能力。但由于鏈接狀態(tài)路由算法需要占用更多的 CPU和內(nèi)存資源，因此，它比距離向量路由算法更難以支持和 實(shí)現(xiàn)。由于大多數(shù)網(wǎng)絡(luò)通信發(fā)生在小公司群 (域 )中，且域內(nèi)路由器只需 要了解域內(nèi)的其他路由器即可。靜態(tài)路由選擇算法設(shè)計(jì) 0 單，并在網(wǎng)絡(luò)信息流相對(duì)可以預(yù)見且網(wǎng)絡(luò)設(shè) 計(jì)相對(duì)簡(jiǎn)單的環(huán)境里效果較好。路由選擇算法必須具有強(qiáng)壯性，這意味著他們必須在出現(xiàn)異?；蚍穷A(yù)見性情況時(shí)（如硬件故障，高負(fù)荷狀態(tài)和不正確的操作）也能正常運(yùn)行。轉(zhuǎn)發(fā)策略稱為路由選擇，這也是路由器名稱由來。 近幾年的研究表明網(wǎng)絡(luò)路由算法對(duì)實(shí)現(xiàn)網(wǎng)絡(luò)保證質(zhì)量的服務(wù)起到了非常關(guān)鍵的作用。 1． 設(shè)計(jì)目標(biāo) 路由選擇算法通常具有下列一個(gè)或多個(gè)設(shè)計(jì)要求： （ 1） 最優(yōu)性。路由選擇算法收斂過慢，會(huì)導(dǎo)致路由循環(huán)或網(wǎng)絡(luò)發(fā)生故障。 2)單路徑和多路徑路由選擇算法 ． 一些復(fù)雜的路由選擇協(xié)議支持多路徑到達(dá)同一目的節(jié)點(diǎn)，與單路徑算法不同，這些 i路徑算法允許信息流在多條線上進(jìn)行復(fù)制。 雖然主機(jī)智能路由選擇算 法在實(shí)際發(fā)送數(shù)據(jù)包之前就能發(fā)現(xiàn)到達(dá)目的節(jié)點(diǎn)的所有可能的路由，并能根據(jù)不同系統(tǒng)對(duì)最優(yōu)路由的不同要求做出選擇，但這種選擇所有路徑的方法常常需要耗費(fèi)大量的時(shí)間。 （ 2） 可靠性。當(dāng)然，持續(xù)不斷堤監(jiān)控這些負(fù)載參數(shù)本身就會(huì)占用資源。 在 我們能夠找到公平性與最優(yōu)性間的平衡辦法之前，必須確定要對(duì)什么進(jìn)行優(yōu)化。 （ 2） 使 Kv← true。 圖 圖 的最短路徑圖 Dijkstra 算法實(shí)現(xiàn) Dijkstra 算法利用了 TableEntry 數(shù)據(jù)結(jié)構(gòu)，每個(gè) TableEntry 具有 known、 distance、predecessor 三個(gè)域，對(duì)應(yīng)變量 Kv， dv， pv。 ArrayTableEntrytable(n)。 edge=dynamic_castWeightedEdgeamp。 } delete amp。在上述離子中， Kruskal 算法