《数据结构》 (java版) 课件 9-2有向带权图的最短路径

带权有向图的最短路径bcdefgah253-46-33-6487路径长度：边的权重之和例如，a→b→e→h=3-4+4=3两点间的最短路径：两点间路径长度最短的路径。例如，𝜹(a,e)=-1,𝜹(a,f)=11负权环：环中边的权重之和为负数例如，d«︎g=3-6=-3负权环使得两点间的最短路径无定义:

例如，𝜹(a,h)=-∞𝜹(a,g)=-∞最短路径的性质最短路径具有最优子结构，即最短路径的子路径是最短路径：设p=≺v1,v2,...,vk≻是从v1到vk的最短路径，对于任意的i,j，其中，1≤i≤j≤k，设pij=≺vi,vi+1,...,vj≻为p中从顶点vi到顶点vj的子路径。那么pij是从vi到vj的最短路径。证明：如果将路径p分解为v1⤳vi⤳vj⤳vk，则有w(p)=w(p1i)+w(pij)+w(pjk)。假设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算法:无负权重的边，时间复杂度取决于优先队列的实现技术DAG(有向无环图)的算法：O(|V|+|E|)v0是无负权环的有向图G的一个顶点，求v0到G中所有其它顶点的最短路径：Dijkstra算法荷兰计算机科学家Dijkstra（1930年5月11日~2002年8月6日）1972年获得素有计算机科学界的诺贝尔奖之称的图灵奖1提出“goto有害论”;2提出信号量和DV原语;3解决了“哲学家聚餐”问题;4最短路径算法(SDF)和银行家算法的创造者;5第一个Algol60编译器的设计者和实现者;6THE操作系统的设计者和开发者;与D.E.Knuth并称为我们这个时代最伟大的计算机科学家。摘自：百度百科Dijkstra算法假设v0到vk的最短路径为：v0⤳vj→vk

根据最优子结构，v0⤳vj一定是v0到vj的最短路径；由于边的权重≥0，v0⤳vj一定不比v0⤳vk长直觉上：按照由短到长的次序求v0到其它顶点的最短路径如果已经求出了v0到v1、v2、...、vj的最短路径，则下一条最短路径按以下的方式产生：v0⤳vk=min{v0⤳vi→vk，i=1,2,...,j，<vi,vk>∈E}d[]：源点v0到顶点的距离p[]：使得d[]变短的顶点S：已经求出最短路径的顶点集合Q:存放顶点的最小优先队列，按照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|次如果采用线性表实现优先队列，则出队操作O(|V|)，O(|V|2+|E|)=>O(|V|2)如果采用二叉堆，O(|V|log|V|+|E|)Dijkstra算法数据结构对算法的影响？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算法-数组实现

private

voiddijkstraWithArray(int

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

int[]S=new

int[n];//S[i]=0，表示还没有求出结点source到结点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算法-数组实现

//扩展找到的这条最短路径 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算法使用优先队列(二叉堆)java类库的PriorityQueue并不适合用于Dijkstra算法，因为数据的优先级发生了变化，要重新调整堆=>增加新操作：decreaseprivate

voidsiftUp(int

k,Tx)//需要知道位置如果知道优先级减少的数据在堆中的位置：public

voiddecrease(int

k){ Te=Tqueue[k]; siftUp(k,e);}Dijkstra算法使用的优先队列对数据进行包装：增加在堆中的位置堆的操作要设置数据在堆中的位置优先级减少的数据在堆中的位置？二叉堆数组包装数据intposition2Tvalueintposition1Tvalueintposition0Tvalue新的优先队列

//Entry将数据T封装，增加了在堆中的位置

public

static

classEntry<T>{

private

int

position=0;//堆中的位置

privateTvalue;//数据，可以比较大小

publicEntry(Tvalue){

this.value=value; }

public

intgetPosition(){

return

position; }

public

voidsetValue(Tvalue){

this.value=value; }

publicTgetValue(){

return

value; }

publicStringtoString(){

return

position+":"+value; } }新的优先队列public

classPriorityQueueWithDecrease<T>{

privateObject[]queue;

private

int

size=0;//Entry将数据T封装，增加了在堆中的位置

public

static

classEntry<T>{...}

publicPriorityQueueWithDecrease(int

maxSize){

queue=newObject[maxSize]; }

//新增加的方法，减少位置k的数据的优先级，需要重新调整堆

@SuppressWarnings("unchecked")

public

voiddecrease(int

k){ Entry<T>e=(Entry<T>)queue[k]; siftUp(k,e); }新的优先队列

private

voidsiftDown(int

k,Entry<T>x){ Comparable<?superT>key=(Comparable<?superT>)x.value;

int

half=size>>>1;

while(k<half){

int

child=(k<<1)+1; Entry<T>c=(Entry<T>)queue[child];

int

right=child+1;

if(right<size&&((Comparable<?superT>)c.value).compareTo(((Entry<T>)queue[right]).value)>0)

c=(Entry<T>)queue[child=right];

if(key.compareTo(c.value)<0)

break;

c.position=k;//设置堆的位置

queue[k]=c;

k=child; }

x.position=k;//设置堆的位置

queue[k]=x; }新的优先队列

private

voidsiftUp(int

k,Entry<T>x){ Comparable<?superT>key=(Comparable<?superT>)x.value;

while(k>0){

int

parent=(k-1)>>>1; Entry<T>e=(Entry<T>)queue[parent];

if(key.compareTo(e.value)>0)

break;

e.position=k;//设置堆的位置

queue[k]=e;

k=parent; }

x.position=k;//设置堆的位置

queue[k]=x; }新的优先队列

public

static

voidmain(String[]args){ Integer[]distance={5,8,1,10,2,9,7,6,4,3,10};//11个 PriorityQueueWithDecrease<Integer>queue=

newPriorityQueueWithDecrease<>(distance.length); Entry<Integer>[]data=(Entry<Integer>[])newEntry<?>[distance.length];

for(int

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

data[i]=newEntry<Integer>(distance[i]);

queue.offer(data[i]); }

queue.display();

data[10].setValue(-1);

queue.decrease(data[10].getPosition());

queue.display();

while(queue.size!=0){ Integerp=queue.poll(); System.out.print(p+""); } System.out.println(); }}0:11:22:53:44:35:96:77:108:69:810:100:-11:12:53:44:25:96:77:108:69:810:3-112345678910Dijkstra算法-优先队列实现

private

voiddijkstraWithPriorityQueueWithDecreaseKey(int

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

classPairimplementsComparable<Pair>{//ppt中的数组d[]的1个数组元素：下标和距离

int

vertex;

double

distance; Pair(int

v,double

d){

vertex=v;

distance=d; }

public

intcompareTo(Pairrhd){

returnDpare(distance,rhd.distance); } }Dijkstra算法-优先队列实现 PriorityQueueWithDecrease<Pair>queue=newPriorityQueueWithDecrease<>(n); Entry<Pair>[]data=newEntry[n];

int[]S=new

int[n];

for(int

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

path[i]=-1;

S[i]=0;

if(i!=source)

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

else

data[i]=newEntry<>(newPair(i,0.0));

queue.offer(data[i]); }Dijkstra算法-优先队列实现

//对队列操作

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

int

u=queue.poll().vertex;

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

while(it.hasNext()){

int

v=it.next();

double

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

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

data[v].getValue().distance=sum;

queue.decrease(data[v].getPosition());

path[v]=u; } } }

for(int

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

distance[i]=data[i].getValue().distance; }偶(对)堆-paringheap偶堆是满足堆条件的m叉树。1146810253971315161814121719偶堆-paringheap归并：将具有较大根的堆作为具有较小根的堆的新的第一个孩子。插入：归并的特例。decrease：将以权变小的结点为根的树从原树删除，再归并。偶堆-paringheap例如，结点的权由5改为1。将以5为根的树从原树中分离，作为一个新堆，再与原有的堆合并。4681023971312171914111151618偶堆-paringheap1111516184681023971312171914偶堆-paringheap删除：将根结点的孩子结点从左到右两两合并，再从右往左逐一合并删除2，从左往右合并：468103713191151516189141217偶堆-paringheap从右往左合并：610313481151516187199141217偶堆-paringheap继续合并：610313481151516187199141217偶堆-paringheap偶堆在实现时可以采用孩子-兄弟表示法，使用三叉链表将距离数据作为T直接存入结点

public

nodeoffer(T)//输入：权重，返回：存放这个权的结点

publicTpoll()

publicvoiddecrease(node,T)//修改node的权重偶堆的删除操作的时间复杂度O(n)，其它操作都是O(1)一系列操作的均摊时间复杂度可能是O(logn)动态规划通过组合子问题的解而解决整个问题。通过记录重复子问题的解，避免重复计算，从而减少时间复杂度动态规划Fibonacci数列：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); }动态规划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求无负权环的有向图G(权值可以为负)的每对顶点之间的最短路径：𝜹(1,1)、𝜹(1,2)、𝜹(1,3)𝜹(2,1)、𝜹(2,2)、𝜹(2,3)𝜹(3,1)、𝜹(3,2)、𝜹(3,3)Floyd-Warshall算法将有向带权图的顶点任意编号为:1、2、...、n设pij=≺vi,vi1,vi2,...,vik...,vj≻为从顶点vi到顶点vj的最短路径设k是中间顶点(除i和j)中的最大编号，则pij可以改写为pikpkj由于最短路径具有最优子结构的性质，所以𝜹(i,j)=𝜹(i,k)+𝜹(k,j)同理，可以改写pik和pkj...。Vi

Vj

Vk

Vh

Vm

Floyd-Warshall算法这提示我们可以按这样的次序计算子问题:中间顶点最大编号1的最短路径中间顶点最大编号2的最短路径...中间顶点最大编号n的最短路径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算法程序实现时，需要的矩阵：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)结论：只用一个矩阵即可！Floyd-Warshall算法0403∞D11620000000000132326411PFloyd-Warshall算法0403∞D11620加入顶点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∞D11620加入顶点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}=2Floyd-Warshall算法1323264110403∞D11620加入顶点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}=0Floyd-Warshall算法1323264110403∞1162000000-10043710加入顶点1DP3->1,1->2,更改了3->2Floyd-Warshall算法13232641111006620000000004371242加入顶点2DP1->2,2->3,更改了1->3Floyd-Warshall算法1323264116006200000000437122353加入顶点3DP2->3,3->1,更改了2->1Floyd-Warshall算法132326411每对顶点之间的最短路径Floyd-Warshall算法只需要使用简单的数据结构：矩阵Floyd-Warshall算法的时间复杂度为O(|V|3)Johnson算法适用于稀疏图课堂练习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