《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 9-3有向帶權(quán)圖的最短路徑

帶權(quán)有向圖的最短路徑bcdefgah253-46-33-6487路徑長度：邊的權(quán)重之和例如，a→b→e→h=3-4+4=3兩點間的最短路徑：兩點間路徑長度最短的路徑。例如，??(a,e)=-1,??(a,f)=11負權(quán)環(huán)：環(huán)中邊的權(quán)重之和為負數(shù)例如，d??g=3-6=-3負權(quán)環(huán)使得兩點間的最短路徑無定義:

例如，??(a,h)=-∞??(a,g)=-∞最短路徑的性質(zhì)最短路徑具有最優(yōu)子結(jié)構(gòu)，即最短路徑的子路徑是最短路徑：設(shè)p=?v1,v2,...,vk?是從v1到vk的最短路徑，對于任意的i,j，其中，1≤i≤j≤k，設(shè)pij=?vi,vi+1,...,vj?為p中從頂點vi到頂點vj的子路徑。那么pij是從vi到vj的最短路徑。證明：如果將路徑p分解為v1?vi?vj?vk，則有w(p)=w(p1i)+w(pij)+w(pjk)。假設(shè)pij不是從vi到vj的最短路徑，則存在路徑p'ij，w(p'ij)<w(pij)，使用p'ij替換pij得到另外一條v1到vk的路徑p'，有w(p')<w(p)，與p是v1到vk的最短路徑相矛盾。p1ipijpjk單源點到所有其它頂點的最短路徑Bellman-Ford算法:O(|V|×|E|)Dijkstra算法:無負權(quán)重的邊，時間復雜度取決于優(yōu)先級隊列的實現(xiàn)技術(shù)DAG(有向無環(huán)圖)的算法：O(|V|+|E|)v0是無負權(quán)環(huán)的有向圖G的一個頂點，求v0到G中所有其它頂點的最短路徑：Dijkstra算法荷蘭計算機科學家Dijkstra（1930年5月11日~2002年8月6日）1972年獲得素有計算機科學界的諾貝爾獎之稱的圖靈獎1提出“goto有害論”;2提出信號量和DV原語;3解決了“哲學家聚餐”問題;4最短路徑算法(SDF)和銀行家算法的創(chuàng)造者;5第一個Algol60編譯器的設(shè)計者和實現(xiàn)者;6THE操作系統(tǒng)的設(shè)計者和開發(fā)者;與D.E.Knuth并稱為我們這個時代最偉大的計算機科學家。摘自：百度百科Dijkstra算法假設(shè)v0到vk的最短路徑為：v0?vj→vk

根據(jù)最優(yōu)子結(jié)構(gòu)，v0?vj一定是v0到vj的最短路徑；由于邊的權(quán)重≥0，v0?vj一定不比v0?vk長直覺上：按照由短到長的次序求v0到其它頂點的最短路徑如果已經(jīng)求出了v0到v1、v2、...、vj的最短路徑，則下一條最短路徑按以下的方式產(chǎn)生：v0?vk=min{v0?vi→vk，i=1,2,...,j，<vi,vk>∈E}d[]：源點v0到頂點的距離p[]：使得d[]變短的頂點S：已經(jīng)求出最短路徑的頂點集合Q:存放頂點的最小優(yōu)先級隊列，按照d[]比較大小Dijkstra算法1、初始化:d[v0]=0，d[vi]=∞;p[i]=-1;S=?；Q=V2、whileQ≠?{3、從Q中取出頂點u，u的d[u]最小4、S=S∪{u}5、foru的鄰接點v，且v?S，6、ifd[v]>d[u]+w(u,v)thend[v]=d[u]+w(u,v)，p[v]=u;?Relax}Dijkstra算法v11001010550v0v2v5v460v32030-1-1-1-1-1-1∞0∞∞∞∞d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={}Q={v0,v1,v2,v3,v4,v5}Dijkstra算法v1出隊：Relax(v1,v2)、Relax(v1,v4)、Relax(v1,v5)-1-1-1-1-1-1∞0∞∞∞∞d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={}Q={v0,v1,v2,v3,v4,v5}-1-11-111∞010∞30100d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1}Q={v0,v2,v3,v4,v5}v11001010550v0v2v5v460v32030Dijkstra算法v2出隊：Relax(v2,v3)-1-11-111∞010∞30100d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1}Q={v0,v2,v3,v4,v5}-1-11211∞0106030100d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2}Q={v0,v3,v4,v5}v11001010550v0v2v5v460v32030Dijkstra算法v4出隊：Relax(v4,v3)、Relax(v4,v5)-1-11414∞010503090d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2,v4}Q={v0,v3,v5}-1-11211∞0106030100d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2}Q={v0,v3,v4,v5}v11001010550v0v2v5v460v32030Dijkstra算法v3出隊：Relax(v3,v5)-1-11414∞010503090d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2,v4}Q={v0,v3,v5}-1-11413∞010503060d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2,v4,v3}Q={v0,v5}v11001010550v0v2v5v460v32030Dijkstra算法v5出隊v0出隊-1-11413∞010503060d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2,v4,v3}Q={v0,v5}-1-11413∞010503060d[0]d[1]d[2]d[3]d[4]d[5]v0v1v2v3v4v5p[0]p[1]p[2]p[3]p[4]p[5]S={v1,v2,v4,v3,v5}Q={v0}S={v0,v1,v2,v4,v3,v5}Q={}v11001010550v0v2v5v460v32030課堂練習533424521481出隊操作|V|次，Relax操作|E|次如果采用線性表實現(xiàn)優(yōu)先級隊列，則出隊操作O(|V|)，O(|V|2+|E|)=>O(|V|2)如果采用二叉堆，O((|V|+|E|)log|V|)Dijkstra算法數(shù)據(jù)結(jié)構(gòu)對算法的影響？Dijkstra算法

public

static

voidmain(String[]args){ Character[]weightedData={'0','1','2','3','4','5'}; IGraph<Character>weightedGraph=

newLinkedListWeightedDirectGraph<>(weightedData);

weightedGraph.addWeightedEdge(0,2,5.0);

weightedGraph.addWeightedEdge(1,2,10.0);

weightedGraph.addWeightedEdge(1,4,30.0);

weightedGraph.addWeightedEdge(1,5,100.0);

weightedGraph.addWeightedEdge(2,3,50.0);

weightedGraph.addWeightedEdge(3,5,10.0);

weightedGraph.addWeightedEdge(4,3,20.0);

weightedGraph.addWeightedEdge(4,5,60.0); GraphAlgorithms<Character>weightedPathAlg=newGraphAlgorithms<>(weightedGraph);

weightedPathAlg.dijkstra(1); }Dijkstra算法

public

voiddijkstra(int

source){

if(graph.getGraphKind()!=GraphKind.WeightedDirectGraph)

return;

double[]distance=new

double[n];

int[]path=new

int[n];

//dijkstraWithArray(source,distance,path); dijkstraWithPriorityQueueWithDecreaseKey(source,distance,path);

//以下求源點到各點的路徑上的點

int[]tmp=new

int[n];

for(int

i=0;i<n;i++){

int

count=0;

int

back=i;

while(path[back]!=-1)

tmp[count++]=back=path[back]; System.out.print(source);

for(int

j=count-2;j>=0;j--) System.out.print("->"+tmp[j]); System.out.println("->"+i+""+distance[i]); } }1->0Infinity1->10.01->210.01->4->350.01->430.01->4->3->560.0Dijkstra算法-數(shù)組實現(xiàn)

private

voiddijkstraWithArray(int

source,double[]distance,int[]path){

int[]S=new

int[n];//S[i]=0，表示還沒有求出結(jié)點source到結(jié)點i的最短距離

for(int

i=0;i<S.length;i++){

path[i]=-1;

distance[i]=Double.POSITIVE_INFINITY; }

distance[source]=0.0;//？？？

int

count=n;

while(count--!=0){

int

u=Integer.MAX_VALUE;//任意值

double

min=Double.POSITIVE_INFINITY;

//查找目前的最短路徑

for(int

i=0;i<n;i++){

if(S[i]==0&&distance[i]<=min){//必須<=，因為min的初值是無窮大

u=i;

min=distance[i]; } }

S[u]=1;Dijkstra算法-數(shù)組實現(xiàn)

//擴展找到的這條最短路徑 Iterator<Integer>it=graph.iterator(u);

while(it.hasNext()){

int

v=it.next();

double

sum=distance[u]+graph.getWeight(u,v);

if(S[v]==0&&distance[v]>sum){

distance[v]=sum;

path[v]=u; } } } }Dijkstra算法-優(yōu)先級隊列實現(xiàn)

private

voiddijkstraWithPriorityQueue(int

source,double[]distance,int[]path){

classVerteximplementsComparable<Vertex>{

int

id;//頂點編號

double

d;//d值 Vertex(int

v,double

d){

id=v;

this.d=d; }

public

intcompareTo(Vertexrhd){//頂點的大小由d值決定

returnDpare(d,rhd.d); }}Dijkstra算法-優(yōu)先級隊列實現(xiàn)

//queueppt中的Q PriorityQueueWithDecrease<Vertex>queue=newPriorityQueueWithDecrease<>(n);

@SuppressWarnings("unchecked") Entry<Vertex>[]data=(Entry<Vertex>[])newEntry<?>[n];//引用所有的頂點

//初始化部分

int[]S=new

int[n];//初始化S，S為空集

for(int

i=0;i<n;++i){//初始化隊列Q，包含所有的頂點

path[i]=-1;

if(i!=source)

data[i]=newEntry<>(newVertex(i,Double.POSITIVE_INFINITY));

else

data[i]=newEntry<>(newVertex(i,0.0));//源點，d值=0

queue.offer(data[i]);//頂點入隊 }Dijkstra算法-優(yōu)先級隊列實現(xiàn)

while(queue.size()!=0){

int

u=queue.poll().id;//具有最小d值的頂點u

S[u]=1;//S=S∪{u} Iterator<Integer>it=graph.iterator(u);

while(it.hasNext()){

int

v=it.next();//u→v的弧

if(S[v]==0){

//Relax(u,vwuv)

if(data[v].data.d>data[u].data.d+graph.getWeight(u,v)){

data[v].data.d=data[u].data.d+graph.getWeight(u,v);

queue.decrease(data[v]);

path[v]=u;//在源點到v的最短路徑上，u是v的前驅(qū) } } } }

for(int

i=0;i<n;++i)//獲取各頂點的d值

distance[i]=data[i].data.d; }動態(tài)規(guī)劃通過組合子問題的解而解決整個問題。通過記錄重復子問題的解，避免重復計算，從而減少時間復雜度動態(tài)規(guī)劃Fibonacci數(shù)列：1,1,2,3,5,8,...fibonacci(n)=1n=1或n=2fibonacci(n-1)+fibonacci(n-2)n>2

public

intfibonacci(int

n){

if(n==1||n==2)

return1;

else

returnfibonacci(n-1)+fibonacci(n-2); }動態(tài)規(guī)劃f(5)f(3)f(4)f(1)f(2)f(3)f(1)f(2)f(2)有多個重復子問題自頂向下自底向上

public

static

intfibonacci(int

n){

if(n==1||n==2)return1;

int[]fib=new

int[n+1];

fib[1]=fib[2]=1;

for(int

i=3;i<=n;i++)

fib[i]=fib[i-1]+fib[i-2];

return

fib[n]; }每對頂點之間的最短路徑132326411求無負權(quán)環(huán)的有向圖G(權(quán)值可以為負)的每對頂點之間的最短路徑：??(1,1)、??(1,2)、??(1,3)??(2,1)、??(2,2)、??(2,3)??(3,1)、??(3,2)、??(3,3)Floyd-Warshall算法將有向帶權(quán)圖的頂點任意編號為:1、2、...、n設(shè)pij=?vi,vi1,vi2,...,vik...,vj?為從頂點vi到頂點vj的最短路徑設(shè)k是中間頂點(除i和j)中的最大編號，則pij可以改寫為pikpkj由于最短路徑具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，所以??(i,j)=??(i,k)+??(k,j)同理，可以改寫pik和pkj...。Vi

Vj

Vk

Floyd-Warshall算法Vi

Vj

V2Vi

Vj

V1Vj

Vi

Vj

Vi

Vj

V3Vi

Vj

Vn……Floyd-Warshall算法這提示我們可以按這樣的次序計算子問題:中間頂點最大編號1的最短路徑中間頂點最大編號2的最短路徑...中間頂點最大編號n的最短路徑Floyd-Warshall算法A=B×CA[i,j]=∑B[i,k]×C[k,j]A[i,j]=B[i,k]+C[k,j]矩陣乘法最短路徑1、初始化：2、求出后，求:頂點i和頂點j之間，中間頂點最大編號為k的最短路徑=w(i,j)=min(

,)+3、當k=n時，就是i和j之間的最短路徑Floyd-Warshall算法=(1)Vi

Vj

Vk

1……k-1=+(2)Vi

Vj

Vk

1……k-11……k-1Floyd-Warshall算法程序?qū)崿F(xiàn)時，需要的矩陣：Dij(0)Dij(1)Dij(2)......Dij(k-1)Dij(k)...因為：Dkj(k)=min(Dkj(k-1),Dkk(k-1)+Dkj(k-1))=Dkj(k-1)Dik(k)=min(Dik(k-1),Dik(k-1)+Dkk(k-1))=Dik(k-1)注意Dkk(k-1)為0矩陣所以：Dij(k)=min(Dij(k-1),Dik(k-1)+Dkj(k-1))=min(Dij(k-1),Dik(k)+Dkj(k))距離不變:Dij(k)=Dij(k-1)?Dij(k)=Dij(k)距離改變:Dij(k)=Dik(k-1)+Dkj(k-1)=Dik(k)+Dkj(k)結(jié)論：只用一個矩陣即可！Floyd-Warshall算法0403∞D(zhuǎn)11620000000000132326411PFloyd-Warshall算法0403∞D(zhuǎn)11620加入頂點1D[1,1]=min{D[1,1],D[1,1]+D[1,1]}=min{0,0+0}=0D[1,2]=min{D[1,2],D[1,1]+D[1,2]}=min{4,0+4}=4D[1,3]=min{D[1,3],D[1,1]+D[1,3]}=min{11,0+11}=11Floyd-Warshall算法1323264110403∞D(zhuǎn)11620加入頂點1D[2,1]=min{D[2,1],D[2,1]+D[1,1]}=min{6,6+0}=6D[2,2]=min{D[2,2],D[2,1]+D[1,2]}=min{0,6+4}=0D[2,3]=min{D[2,3],D[2,1]+D[1,3]}=min{2,6+11}=2132326411Floyd-Warshall算法0403∞D(zhuǎn)11620加入頂點1D[3,1]=min{D[3,1],D[3,1]+D[1,1]}=min{3,3+0}=3D[3,2]=min{D[3,2],D[3,1]+D[1,2]}=min{∞,3+4}=7D[3,3]=min{D[3,3],D[3,1]+D[1,3]}=min{0,3+11}=0132326411Floyd-Warshall算法0403∞1162000000-10043710加入頂點1DP3->1,1->2,更改了3->2132326411Floyd-Warshall算法11006620000000004371242加入頂點2DP1->2,2->3,更改了1->3132326411Floyd-Warshall算法6006200000000437122353加入頂點3DP2->3,3->1,更改了2->1132326411Floyd-Warshall算法Floyd-Warshall算法只需要使用簡單的數(shù)據(jù)結(jié)構(gòu)：矩陣Floyd-Warshall算法的時間復雜度為O(|V|3)Johnson算法適用于稀疏圖Floyd-Warshall算法課堂練習533424521481Floyd-Warshall算法

public

voidfloyd(){

if(graph.getGraphKind()!=GraphKind.WeightedDirectGraph)

return;

double[][]distance=new

double[n][n];

int[][]path=new

int[n][n];

//初始化

for(int

i=0;i<n;i++){

for(int

j=0;j<n;j++){

distance[i][j]=graph.getWeight(i,j);

path[i][j]=-1; } }

//因為用無窮大表示無邊，所以頂點到自己的路徑長度為無窮大，矯正

for(int

i=0;i<n;i++)

distance[i][i]=0.0;Floyd-Warshall算法

//核心

for(int

k=0;k<n;k++){

for(int

i=0;i<n;i++){

for(int

j=0;j<n;j++){

double

tmp=distance[i][k]+distance[k][j];

if(tmp<distance[i][j]){

distance[i][j]=tmp;

path[i][j]=k; } } } }Floyd-Warshall算法

//輸出路徑

int[]itoj=new

int[n];

for(int

i=0;i<n;i++){

for(int

j=0;j<n;j++){ System.out.print("path["+i+"]["+j+"]=");

int

pos=rfindpath(itoj,0,i,j,path);

for(int

k=0;k<pos;k++){

if(k!=pos-1) System.out.print(itoj[k]+"->");

else System.out.print(itoj[k]); } System.out.println(""+distance[i][j]); } } }Floyd-Warshall算法

private

intrfindpath(int

itojpath[],int

pos,int

i,int

j,int

path[][]){

int

k=path[i][j];

if(k==-1){

itojpath[pos++]=i;

itojpath[pos++]=j; }else{

int

mid=rfindpath(itojpath,pos,i,k,path);

pos=rfindpath(itojpath,--mid,k,j,path);//覆蓋前面的k，否則有重復的頂點 }

return

pos; }Floyd-Warshall算法

public

static

voidmain(String[]args){ Character[]weightedData={'0','1','2','3','4','5'}; IGraph<Character>weightedGraph=

newLinkedListWeightedDirectGraph<>(weightedData);

weightedGraph.addWeightedEdge(0,2,5.0);

weightedGraph.addWeightedEdge(1,2,10.0);

weightedGraph.addWeightedEdge(1,4,30.0);

weightedGraph.addWeightedEdge(1,5,100.0);

weightedGraph.addWeightedEdge(2,3,50.0);

weightedGraph.addWeightedEdge(3,5,10.0);

weightedGrap