數(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

由頂點集

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

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

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

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

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

算法描述①計算從源點直接到達(dá)各頂點的權(quán)值；③借助步驟②中得到的頂點，計算從源點間接到達(dá)各頂點的權(quán)值之和，如小于①中權(quán)值之和，則替換；②選擇權(quán)值最小的路徑；④重復(fù)步驟②③，直到找到從源點到其余各頂點的最短路徑。三、Dijkstra算法322.算法描述①計算從源點直接到達(dá)各頂點的權(quán)值；③借助步33v1v2v3v4S頂點從V0到各點的最短路徑及其長度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具體實現(xiàn)：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S頂點34v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(xiàn)：v1v0v4v3v210030601010205039v1v2v3v4S10(v40經(jīng)開區(qū)要建一個消防站，如圖所示，其中各頂點表示開發(fā)區(qū)中5個消防重點單位，分析消防站選址問題思考：v1v0v4v3v210030601010205040經(jīng)開區(qū)要建一個消防站，如圖所示，其中各頂點表示開發(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

由頂點集

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

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

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

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

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

算法描述①計算從源點直接到達(dá)各頂點的權(quán)值；③借助步驟②中得到的頂點，計算從源點間接到達(dá)各頂點的權(quán)值之和，如小于①中權(quán)值之和，則替換；②選擇權(quán)值最小的路徑；④重復(fù)步驟②③，直到找到從源點到其余各頂點的最短路徑。三、Dijkstra算法322.算法描述①計算從源點直接到達(dá)各頂點的權(quán)值；③借助步74v1v2v3v4S頂點從V0到各點的最短路徑及其長度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具體實現(xiàn)：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S頂點75v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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頂點從V0到各點的最短路徑及其長度3.具體實現(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