數(shù)據(jù)結(jié)構(gòu)最短路徑課件

數(shù)據(jù)結(jié)構(gòu)最短路徑v2V1v4v3132145數(shù)據(jù)結(jié)構(gòu)最短路徑v2V1v4v31321452我想去俱樂部看演出。一、問題描述綜合樓校大門俱樂部圖書館2我想去俱樂部看演出。一、問題描述綜合樓校大門俱樂部圖書館3我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門3我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門4我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門俱樂部4我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門5我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門俱樂部線路二：校大門5我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門我該怎么走呢？6綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院線路一：校大門俱樂部我該怎么6綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門7綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院圖書館我該怎么走呢？線路一：校大門俱樂部7綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院8綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院圖書館我該怎么走呢？線路一：校大門俱樂部俱樂部8綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院9綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院線路一：校大門俱樂部圖書館俱樂部哪條線路最短呢？9綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院10綜合樓俱樂部圖書館一、問題描述v010綜合樓俱樂部圖書館一、問題描述v011俱樂部圖書館一、問題描述v0v111俱樂部圖書館一、問題描述v0v112俱樂部v2一、問題描述v0v112俱樂部v2一、問題描述v0v113俱樂部v2一、問題描述v0v1v313俱樂部v2一、問題描述v0v1v314v4v2一、問題描述v0v1v314v4v2一、問題描述v0v1v315

由頂點(diǎn)集

和邊集所描述的數(shù)據(jù)結(jié)構(gòu)

記作G＝(V，E)其中，V為圖中頂點(diǎn)的非空有限集合

E為圖中有向邊的有限集合G=（V，E）V={v0,v1,v4}E={<v0,v1>,<v0,v4>}二、圖的定義與術(shù)語v1v0v4GG1、圖：15由頂點(diǎn)集和邊集所描述的數(shù)據(jù)16二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列16二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)17二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列17二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)18二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列18二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)19二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列19二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)20二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列20二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)21二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列21二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)22二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列22二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)23二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列23二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)24二、圖的定義與術(shù)語v1v0v4v3v23、權(quán)值：各有向邊所對(duì)應(yīng)的代價(jià)2、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列24二、圖的定義與術(shù)語v1v0v4v3v23、權(quán)值：各有向254、最短路徑：兩點(diǎn)之間權(quán)值之和最小的路徑二、圖的定義與術(shù)語v1v0v4v3v21003060101020503、權(quán)值：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列各有向邊所對(duì)應(yīng)的代價(jià)2、路徑：254、最短路徑：兩點(diǎn)之間權(quán)值之和最小的路徑二、圖的定義與術(shù)26v1v0v4v3v2100306010102050如何求從v0到v4的最短路徑？26v1v0v4v3v2100306010102050如何求27路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4v1v0v4v3v2100306010102050如何求從v0到v4的最短路徑？27路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v028路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4如何求從v0到v4的最短路徑？v1v0v4v3v2100306010102050直接到達(dá)28路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v029路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4如何求從v0到v4的最短路徑？間接到達(dá)直接到達(dá)v1v0v4v3v210030601010205029路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v030v1v0v4v3v2100306010102050如何求從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑？30v1v0v4v3v2100306010102050如何求②下一條最短路徑？31三、Dijkstra算法Dijkstra，荷蘭人。曾在1972年獲得過圖靈獎(jiǎng)。最短路徑算法(SPF)和銀行家算法的創(chuàng)造者1.

基本思想①權(quán)值之和最小的最短路徑？只含一條有向邊，且權(quán)值最?、燮溆嘧疃搪窂剑恐苯訌脑袋c(diǎn)到該點(diǎn)；從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。直接從源點(diǎn)到該點(diǎn)從源點(diǎn)經(jīng)過頂點(diǎn)vi，再到達(dá)該頂點(diǎn)(由兩條有向邊組成)。

按各路徑權(quán)值之和由小到大的順序，產(chǎn)生從源點(diǎn)到其余各頂點(diǎn)的最短路徑。②下一條最短路徑？31三、Dijkstra算法Dijkstr322.

算法描述①計(jì)算從源點(diǎn)直接到達(dá)各頂點(diǎn)的權(quán)值；③借助步驟②中得到的頂點(diǎn)，計(jì)算從源點(diǎn)間接到達(dá)各頂點(diǎn)的權(quán)值之和，如小于①中權(quán)值之和，則替換；②選擇權(quán)值最小的路徑；④重復(fù)步驟②③，直到找到從源點(diǎn)到其余各頂點(diǎn)的最短路徑。三、Dijkstra算法322.算法描述①計(jì)算從源點(diǎn)直接到達(dá)各頂點(diǎn)的權(quán)值；③借助步33v1v2v3v4S頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S頂點(diǎn)34v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050{v0,v1}∞34v1v2v3v4S10(v35v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100i=1i=2頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050(v0,v1,v2)∞35v1v2v3v4S10(v36v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100{v0,v1,v3}i=1i=2頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050(v0,v1,v2)36v1v2v3v4S10(v37v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)90i=1i=2i=3頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v210030601010205037v1v2v3v4S10(v38v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}{v0,v1,v3,v2}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4)i=1i=2i=3i=4頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v210030601010205038v1v2v3v4S10(v39v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}{v0,v1,v3,v2}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4){v0,v1,v3,v2,v4}i=1i=2i=3i=4頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v210030601010205039v1v2v3v4S10(v40經(jīng)開區(qū)要建一個(gè)消防站，如圖所示，其中各頂點(diǎn)表示開發(fā)區(qū)中5個(gè)消防重點(diǎn)單位，分析消防站選址問題思考：v1v0v4v3v210030601010205040經(jīng)開區(qū)要建一個(gè)消防站，如圖所示，其中各頂點(diǎn)表示開發(fā)區(qū)中541Thanks!41Thanks!數(shù)據(jù)結(jié)構(gòu)最短路徑v2V1v4v3132145數(shù)據(jù)結(jié)構(gòu)最短路徑v2V1v4v313214543我想去俱樂部看演出。一、問題描述綜合樓校大門俱樂部圖書館2我想去俱樂部看演出。一、問題描述綜合樓校大門俱樂部圖書館44我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門3我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門45我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門俱樂部4我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門46我該怎么走呢？一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門俱樂部線路二：校大門5我該怎么一、問題描述綜合樓校大門俱樂部圖書館線路一：校大門我該怎么走呢？47綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院線路一：校大門俱樂部我該怎么6綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門48綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院圖書館我該怎么走呢？線路一：校大門俱樂部7綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院49綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院圖書館我該怎么走呢？線路一：校大門俱樂部俱樂部8綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院50綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院線路一：校大門俱樂部圖書館俱樂部哪條線路最短呢？9綜合樓校大門俱樂部圖書館一、問題描述線路二：校大門信息學(xué)院51綜合樓俱樂部圖書館一、問題描述v010綜合樓俱樂部圖書館一、問題描述v052俱樂部圖書館一、問題描述v0v111俱樂部圖書館一、問題描述v0v153俱樂部v2一、問題描述v0v112俱樂部v2一、問題描述v0v154俱樂部v2一、問題描述v0v1v313俱樂部v2一、問題描述v0v1v355v4v2一、問題描述v0v1v314v4v2一、問題描述v0v1v356

由頂點(diǎn)集

和邊集所描述的數(shù)據(jù)結(jié)構(gòu)

記作G＝(V，E)其中，V為圖中頂點(diǎn)的非空有限集合

E為圖中有向邊的有限集合G=（V，E）V={v0,v1,v4}E={<v0,v1>,<v0,v4>}二、圖的定義與術(shù)語v1v0v4GG1、圖：15由頂點(diǎn)集和邊集所描述的數(shù)據(jù)57二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列16二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)58二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列17二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)59二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列18二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)60二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列19二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)61二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列20二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)62二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列21二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)63二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列22二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)64二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列23二、圖的定義與術(shù)語v1v0v4v3v22、路徑：一個(gè)頂點(diǎn)65二、圖的定義與術(shù)語v1v0v4v3v23、權(quán)值：各有向邊所對(duì)應(yīng)的代價(jià)2、路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列24二、圖的定義與術(shù)語v1v0v4v3v23、權(quán)值：各有向664、最短路徑：兩點(diǎn)之間權(quán)值之和最小的路徑二、圖的定義與術(shù)語v1v0v4v3v21003060101020503、權(quán)值：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列各有向邊所對(duì)應(yīng)的代價(jià)2、路徑：254、最短路徑：兩點(diǎn)之間權(quán)值之和最小的路徑二、圖的定義與術(shù)67v1v0v4v3v2100306010102050如何求從v0到v4的最短路徑？26v1v0v4v3v2100306010102050如何求68路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4v1v0v4v3v2100306010102050如何求從v0到v4的最短路徑？27路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v069路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4如何求從v0到v4的最短路徑？v1v0v4v3v2100306010102050直接到達(dá)28路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v070路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v0v1v2v4v0v3v2v4如何求從v0到v4的最短路徑？間接到達(dá)直接到達(dá)v1v0v4v3v210030601010205029路徑一：v0v4路徑二：路徑三：路徑四：v0v3v4v071v1v0v4v3v2100306010102050如何求從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑？30v1v0v4v3v2100306010102050如何求②下一條最短路徑？72三、Dijkstra算法Dijkstra，荷蘭人。曾在1972年獲得過圖靈獎(jiǎng)。最短路徑算法(SPF)和銀行家算法的創(chuàng)造者1.

基本思想①權(quán)值之和最小的最短路徑？只含一條有向邊，且權(quán)值最?、燮溆嘧疃搪窂?？直接從源點(diǎn)到該點(diǎn)；從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。直接從源點(diǎn)到該點(diǎn)從源點(diǎn)經(jīng)過頂點(diǎn)vi，再到達(dá)該頂點(diǎn)(由兩條有向邊組成)。

按各路徑權(quán)值之和由小到大的順序，產(chǎn)生從源點(diǎn)到其余各頂點(diǎn)的最短路徑。②下一條最短路徑？31三、Dijkstra算法Dijkstr732.

算法描述①計(jì)算從源點(diǎn)直接到達(dá)各頂點(diǎn)的權(quán)值；③借助步驟②中得到的頂點(diǎn)，計(jì)算從源點(diǎn)間接到達(dá)各頂點(diǎn)的權(quán)值之和，如小于①中權(quán)值之和，則替換；②選擇權(quán)值最小的路徑；④重復(fù)步驟②③，直到找到從源點(diǎn)到其余各頂點(diǎn)的最短路徑。三、Dijkstra算法322.算法描述①計(jì)算從源點(diǎn)直接到達(dá)各頂點(diǎn)的權(quán)值；③借助步74v1v2v3v4S頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S頂點(diǎn)75v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050{v0,v1}∞34v1v2v3v4S10(v76v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100i=1i=2頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050(v0,v1,v2)∞35v1v2v3v4S10(v77v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100{v0,v1,v3}i=1i=2頂點(diǎn)從V0到各點(diǎn)的最短路徑及其長度3.具體實(shí)現(xiàn)：v1v0v4v3v2100306010102050(v0,v1,v2)36v1v2v3v4S10(v78v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50