資源描述：
《最短路徑問題ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、最短路徑問題基本概念最短路徑問題的3種類型單源最短路徑問題：找出從每一節(jié)點v到某指定節(jié)點u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問題轉化為單源最短路徑問題。單對節(jié)點間的最短路徑問題：對于給定節(jié)點對u和v，找出從u到v的一條路徑。每對節(jié)點間的最短路徑問題：對于每對節(jié)點u和v，找出從u到v的最短路徑?？梢允褂肍loyed-Warshall算法解決問題，但時間效率底下，且有不能出現(xiàn)負權回路的苛刻條件。不妨以每個節(jié)點為源點運行一次單源算法，以提高時效。松弛技術是單源算法的核心所謂松弛技術，就是反復減小每個節(jié)點的實際最短路徑的權的
2、上限，直到該上限等于最短路徑的權為止。定理：給定有向加權圖G=（V，E），設P=為從節(jié)點V1到節(jié)點Vk的一條路徑，對任意i，j有i<=j<=k，設Pij=為Vi到Vj的P的子路徑，則Pij是從Vi到Vj的一條最短路徑。給定有向加權圖G=（V，E），源點為s，則對于所有邊（u,v）∈E，有&（s，v）<=&（s，u）+w（u,v）。松弛技術對每個節(jié)點v∈V，設置一個屬性d[v]來描述從源點s到v的最短路徑的權的上界，稱之為最短路長估計，設置f[v]表示v點的父親。Procinitia
3、llze_single_source(G,s);{foreachv∈V[G]do{d[v]:=∞;f[v]=nil;}d[s]:=0;}松弛一條邊（u,v）的過程包括測試是否可通過節(jié)點u對目前找出的到v的最短路徑進行改進，如果可能則更新d[v]和f[v]，一次松弛操作可以減小最短路長估計d[v]并更新v的父親f[v]。Procrelax(u,v,w);{ifd[v]>d[u]+w[u,v]then{d[v]:=d[u]+w[u,v];f[v]:=u;}}Dijkstra算法Dijkstra算法解決了有向加權圖的最短路徑問題，該算法的條
4、件是該圖所有邊的權值非負，即對于每條邊(u,v)∈E，w(u,v)>=0;Dijkstra算法中設置了一節(jié)點集合S，從源節(jié)點r到集合S中節(jié)點的最終最短路徑的權均已確定，即對所有節(jié)點v∈S，有d[v]=&(r,v)，并設置了最小優(yōu)先隊列Q，該隊列包含所有屬于V-S的節(jié)點（即這些節(jié)點尚未確定最短路徑的權），且以d值為關鍵字排列各節(jié)點。初始時，Q包含了除r外的其他節(jié)點，這些節(jié)點的d值為∞。r進入集合S，d[r]=0。算法反復從Q中取出d值最小的節(jié)點u∈V-S，把u插入集合S中，并對u的所有出邊進行松弛。這一過程一直進行到Q隊列為空為止。只要
5、圖中沒有負權邊，Dijkstra算法能夠順利完成。如果任何一條邊的權值為負，則算法可能得出錯誤的答案。ProcedureDijstra(G,w,r);{initiallze_single_source(G,r);S:=∮;Q:=V[G];whileQ<>∮do{從最小優(yōu)先隊列Q中取出d值最小的節(jié)點u；S:=S∪[u];forv∈adj(u)dorelax(u,v,w);}}Dijkstra算法的執(zhí)行速度取決于優(yōu)先隊列Q的數(shù)據結構。有3種數(shù)據結構可供選擇：（1）用一維數(shù)組實現(xiàn)優(yōu)先隊列，時間復雜度為O（V*V）。使用于規(guī)模不大的稠密圖。（
6、2）用二叉堆來實現(xiàn)優(yōu)先隊列Q，時間復雜度為O（ElnV），使用于稀疏圖。（3）用Fibonacci堆實現(xiàn)優(yōu)先隊列，時間復雜度優(yōu)化為O（VlnV+E）。但Fibonacci堆的程序實現(xiàn)相當繁瑣，程序的實際運行效果不理想，不推薦使用。Dijkstra算法與Prim算法的異同：同：都是屬于寬度優(yōu)先搜索，且優(yōu)先隊列Q都是以距離d為關鍵字排列的，節(jié)點出隊后都要進行松弛操作。異：Dijkstra算法中的距離d是節(jié)點與源點間最短路長估計值，Prim算法中的距離d是節(jié)點連接生成樹的最短邊長。變形求出最短路的路徑對于多條最短路存在的情況，求方案數(shù)求次短
7、路徑DijkstraP1398Car的旅行路線P1577最佳路線Poj3013BigChristmasTreePoj1135DominoEffect負權回路影響單源最短路徑的計算在某些單源最短路徑問題中，可能存在權為負的邊。如果圖G（V,E）不包含由源s可達的負權回路，則對所有v∈Vs，最短路徑的權的定義&(s,v)依然正確，即使它是一個負值也是如此。但如果存在一個從s可達的負權回路，最短路徑的定義就不能成立了。從s到該回路上的節(jié)點不存在最短路徑，因為我們總可以順著找出的“最短”路徑再穿過負權回路，從而獲得一個權值更小的路徑，因此如果
8、從s到v的某路徑中存在一個負權回路，我們定義&(s,v)=-∞。Bellman-Ford算法Bellman-Ford算法能在更一般的情況下解決單源點最短路徑問題，在該算法中邊的權可以為負。Bellman-Ford算法同樣
