離散數(shù)學(xué)ch04圖論最短路徑與關(guān)鍵路徑-展示頁(yè)
2025-01-27 02:22本頁(yè)面
【正文】 ∞ ∞ 9 9 14 最短路徑及關(guān)鍵路徑 ?試用 Dijkstra算法求下列簡(jiǎn)單無(wú)向賦權(quán)圖中 V1到 V11的最短路徑。 ?vi?T ： d(vi)= d(vl)+W(vl,vi) 若 d(vl)+W(vl,vi)d(vi) d(vi) 否則 最短路徑及關(guān)鍵路徑 ? Step4： 重復(fù)（ 2）和（ 3），直到 vn改為 P標(biāo)號(hào)為止。若為 vl，則將 vl的 T標(biāo)號(hào)改為P標(biāo)號(hào)，且 P=P∪{v l}， T=T{vl}。當(dāng)結(jié)點(diǎn) vn已被改為 P標(biāo)號(hào)時(shí)，就找到了一條從 v1到 vn的最短路徑。所謂結(jié)點(diǎn) v的 P標(biāo)號(hào)是指從 v1到 v的最短路徑的長(zhǎng)度；而頂點(diǎn) u的 T標(biāo)號(hào)是指從 v1到 u某條路徑的長(zhǎng)度。 最短路徑及關(guān)鍵路徑 ? 從源點(diǎn)到其余各點(diǎn)的最短路徑 Dijkstra算法 （ 1959） 設(shè) G有 n個(gè)頂點(diǎn)；邊的長(zhǎng)度 ?ij≥0 ；若結(jié)點(diǎn) vi和 vj沒(méi)有邊相連 (不是鄰接點(diǎn) )，則令 ?ij=∞ ，對(duì)每個(gè)結(jié)點(diǎn) vi，令 ?ij=0。 最短路徑及關(guān)鍵路徑 其余最短路徑的特點(diǎn)： 再 下一條路徑長(zhǎng)度次短的 最短路徑 的特點(diǎn) : 它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v1，再到達(dá)該頂點(diǎn) (由兩條弧組成 )；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v2，再到達(dá)該頂點(diǎn)。 v2 最短路徑及關(guān)鍵路徑 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。離散數(shù)學(xué) Discrete Mathematics 計(jì)算機(jī)與信息工程學(xué)院 第 4章 圖 論 內(nèi)容提要 圖的基本概念 連通圖 圖的矩陣表示 路和回路 內(nèi)容提要 歐拉圖和哈密頓圖 二部圖及匹配 平面圖 樹(shù) ?定義： 設(shè) G=(V， E， ?)為無(wú)向簡(jiǎn)單圖，對(duì)于每一條邊 e∈E ，均有一個(gè)正實(shí)數(shù) W(e)與之對(duì)應(yīng)，稱 w為 G的權(quán)函數(shù)，并稱 G為帶有權(quán) W的圖，又稱賦權(quán)圖，權(quán)也稱為邊的長(zhǎng)度。 最短路徑及關(guān)鍵路徑 邊 (vi,vj)的權(quán) 帶權(quán)圖 求給定兩點(diǎn)間的最短距離 —— 兩點(diǎn)之間的最短路徑問(wèn)題 求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 每一對(duì)頂點(diǎn)之間的最短路徑 最短路徑及關(guān)鍵路徑 求 從源點(diǎn)到其余各點(diǎn)的最短路徑 的算法的基本思想 : 依最短路徑的長(zhǎng)度遞增的次序求得各條路徑 源點(diǎn) v1 … 其中， 從源點(diǎn)到頂點(diǎn) v1的最短路徑 是所有最短路徑中長(zhǎng)度最短者。 下一條路徑長(zhǎng)度 次短的最短路徑 的特點(diǎn)
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1