源码学院-算法与数据结构最短路径

最短路径最短路径介绍Dijkstra算法Bellman

Ford算法最短路径问题最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。（有向带权图）问题解法边上权值非负情形的单源最短路径问题（s->图上其他节点的最短路径）Dijkstra算法边上权值为任意值的单源最短路径问题Bellman

Ford算法所有顶点之间的最短路径（动态规划O(n^3))Floyd算法最短路径相关数据结构目标：找出从s节点到其他所有节点的最短路径.路径：s到所有节点的最短路径树(SPT)必定存在可以用2个数组来表示SPT:distTo[v]:s到v的最短路径,100edgeTo[v]：s到v的最短路径上的最后一条边vswxsxwvS->

X->W

->V边松驰-Edge

Relax的高铁是没有开通：700）到西安的距离：800）

->1500到

的最短距离（高铁）2000）松驰边：e=v->w

（西安到distTo[v]:s到v的已知最短路径（distTo[w]:s到w的已知最短路径（edgeTo[w]:s到w如果边e=v→w

给更新distTo[w]和最短路径-最优性性质对于有向带权图G,

distTo[]表示s到各节点的路径，有：distTo[s]

=0

对于其他各个节点，distTo[v]表示某条从s到v的路径长度（对于不可达的节点，该值为无穷大）distTo[v]是最短路径，当且仅当：对于任意一条v到w的边e，都满足：distTo[w]

≤

distTo[v]

+e.weight()最短路径通用算法算法SP(G，s)：distTo[s]初始化为

0对于其他各个节点，distTo[v]初始化为无穷大重复如下操作：松驰G中的任意边，直到不存在有效边为止实现：怎么样选择边来松驰？Dijkstra's

algorithm

(nonnegative

weights)Bellman-Ford

algorithm

(no

negative

cycles)最短路径介绍Dijkstra算法Bellman

Ford算法Dijkstra算法Dijkstra算法求解从顶点v0出发到其它各顶点最短路径。按路径⻓度递增的次序产⽣最短路径，该算法假设所有边的权都⼤于等于零。边上权值非负情形的单源最短路径问题问题的提法：给定一个带权有向图D与源点v，求从v

到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径,Dijkstra提出按路径长度的递增次序,

逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。Dijkstra逐步求解的过程43210150200

10030

1060源点终点最短路径

路径长度v0v1(v0,v1)10v2v3(v0,v3)(v0,v1,v2)

(v0,v3,v2),60,5030v4(v0,v4)(v0,v3,v4)

(v0,v3,v2

,v4)100,90,604210150200

10030

10603distTo[0]

=

0distTo[1]

=

10distTo[2]=

50distTo[3]

=

30distTo[4]

=

90第1步是选择0节点，对它的所出边进行松弛第2步是选择1节点，对它的所出边进行松弛第3步是选择3节点，对它的所出边进行松弛。。。42100

10015030

10603001

2

3

410

50

30

6034220引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点

v0到终点

vi

的最短路径的长度。初始状态：若从源点v0到顶点vi

有边,则dist[i]为该边上的权值；若从源点v0到顶点

vi

无边,则dist[i]为

。假设

S

是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0

出发，中间只经过

S

中的顶点便可到达的那些顶点vx

(vxV-S

)的路径中的一条。每次求得一条最短路径后,其终点vk加入集合S，然后对所有的vi

V-S，修改其dist[i]值。Dijkstra算法可描述如下：①初始化：S

←{v0

};dist[j]

←

Edge[0][j], j

=

1,2,

…,

n-1;//n为图中顶点个数②求出最短路径的长度：dist[k]←min{dist[i]},

i

V-S

;

//s->k就是最短距离S

←

S

U

{

k

};③修改：dist[i]

←

min{

dist[i],

dist[k]

+

Edge[k][i]

},对于每一个

i

V-S

;④判断：若S=V,则算法结束，否则转②。Dijkstra算法中各辅助数组的最终结果短路径的方法:举顶点4为例edgeTo[4]

=

2

edgeTo[2]

=

3edgeTo[3]=0，反过来排列，得到路径0,3,2,4，这就是源点0到终点4的最短路径。0101502203010100

从表中

源点0到终点v的最4603序号顶点1顶点2顶点3顶点4Dist10-,60,503060edgeTo0302Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40----0----0012340----索引堆：Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40----0----1012340----索引堆：Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40----0----1012340----索引堆：33010Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点401060301000----01234010-30100索引堆：031003041Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点401060301000----3012340106030100索引堆：1423010060Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40105030900----201234010503090索引堆：34Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40105030600----401234010503060索引堆：2作业：基于数组、堆实现Dijkstra算法Dijkstra示例01015022030101004603顶点0顶点1顶点2顶点3顶点40105030600----01234010503060索引堆：4最短路径介绍Dijkstra算法Bellman

Ford算法Bellman-Ford算法解决含负权边的带权有向图的单源最短路径问题不能处理带负权环的图(因可以来回走一条负权边)限制条件:要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。1246-190230->3:

20->1->2->3:

10->1->2->3->0:

-7Bellman-Ford算法思想构造一个最短路径长度数组序列dist

1

[u],dist

2

[u],…,dist

n-1[u]

（u=0,1…n-1,n为点数)dist

1

[u]为从源点s到终点u的最多经过1次relax的最短路径长度，并有dist

1

[u]=adj[s][u]；dist

2

[u]为从源点s最多经过两次relax到达终点u的最短路径长度；dist

3

[u]为从源点s出发最多经过不构成负权值回路的三次relax到达终点u的最短路径长度；......dist

n-1

[u]为从源点s出发最多经过不构成负权值回路的n-1次relax到达终点u的最短路径长度；算法的最终目的是计算出distn-1

[u]，为源点v到顶点u的最短路径长度。dist

k

[u]的计算设已经求出

distk-1

[u],u=0,1,…,n-1，即从源点s经过最多不构成负权值回路的k-1次relax到达终点u的最短路径的长度递推公式(求顶点u到源点s的最短路径)：dist

1

[u]

=adj[s][u]；dist

k

[u]=

min{

dist

k-1

[u],

min{

dist

k-1

[j]

+

adj[j][u]

}

},j=0,1,…,n-1,j≠uBellman-Ford算法算法SP(G，s)：distTo[s]初始化为0对于其他各个节点，distTo[v]初始化为无穷大重复V-1次：依次松驰G中的各条边Bellman-Ford算法010150230-101004603边：0->10->30->41->22->43->23->4顶点0

顶点1

顶点2

顶点3

顶点40----0----顶点0顶点1顶点2顶点3顶点401060，5030100，5000->11->2,

3->20->30->4,

2->4顶点0顶点1顶点2顶点3顶点401050304000->13->20->32->4顶点0顶点1顶点2顶点3顶点401050304000->13->20->32->4顶点0顶点1顶点2顶点3顶点401050304000->13->20->32->420Bellman-Ford算法010150230-101004603顶点0顶点1顶点2顶点3顶点40----0----顶点0顶点1顶点2顶点3顶点40103010000->10->30->420队列：0队列：1,

3,

4顶点0顶点1顶点2顶点3顶点4010603010000->11->20->30->4队列：3,

4,

2顶点0顶点1顶点2顶点3顶点401060,5030100,9000->11->2,3->20->30->4,3->4队列：4,

2顶点0顶点1顶点2顶点3顶点401060,5030100,9000->11->2,3->20->30->4,3->4队列：2Bellman-Ford算法010150230-10100460320顶点0顶点1顶点2顶点3顶点401060,5030100,9000->11->2,3->20->30->4,3->4队列：2顶点0顶点1顶点2顶点3顶点401060,5030100,90,4000->11->2,3->20->30->4,3->4,2->4队列：4顶点0顶点1顶点2顶点3顶点401060,50304000->13->20->32->4队列：基于队列的BellmenFord算法怎么来判断有负环的？Dijkstra算法与Bellman-Ford算法的区别Dijkstra算法和Bellman算法思想有很大的区别：Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到S外各顶点的最短路径长度。Bellman-Ford算法在求解过程中，每次循环都要修改所有顶点的

distTo[]，也就是说源点到各顶点最短路径长度一直要到算法结束才确定下来。其他最短路径算法：所有顶点之间的最短路径Floyd问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点

vi

vj，要求求出vi与vj之间的最短路径和最短路径长度。

Floyd算法的基本思想：O(V^3)，动态规划定义一个n阶方阵序列：A(-1),

A(0),

…,

A(n-1).其中

A(-1)

[i][j]

=Edge[i][j