[关闭]
@zhuanxu 2018-02-03T13:53:28.000000Z 字数 1058 阅读 533

algorithms-on-graphs:graph basics 笔记二

algorithms-on-graphs


本文是学习 Algorithms on Graphs 的笔记第2篇。

Paths && lengths

路径长度

无向图两点距离

有向图两点距离

下面定义 distance level

以s为起点,根据距离s不同分level。
下面是有向图的 distance level


时间复杂度

最短路径树-shortest-path tree

Fastest Route

上面介绍了无权重图中任意两点的最短路径,下面介绍有向图中任意两点的最短距离。
我们先给出一个观察:

最优路径上的子路径也是最优的,因为如果子路径不是最优的,就能将子路径替换为另一条最优子路径,此时就不满足最优子路径的假设了。

因此我们就有下面的结论:

下面定义 Relax 操作:

意义是检查边(u,v)是否会缩短到达v的最短距离。

下面我们定义

通过Naive操作,所有的最短路径就都算好了。

上面描述中,怎么能高效的relax all edges就是关键,下面介绍 Dijkstra's 算法。

Dijkstra's Algorithm

Dijkstra's 算法主要思想:

算法流程

一个案例

最短乘积问题

问题描述:有5种货币,彼此之间的汇率如下,我们希望最大化转换:

思路

but上面的一个问题是,我们如果用 Dijkstra 算法,其要求权值为正,此处log后会出现负数,所以不满足Dijkstra算法的要求了。
下面是出现负环的时候问题

那怎么办?我们回到之前的Naive算法,通过不断relax edge的方式,于是就有了下面的方法:

举个例子来说明上面的过程

为了证明上面方法的正确性:为什么循环V-1次后,我们就能找到所有的最短路径了?
我们先给出一个引理:

在第K个循环relax后,最短路径至多包含k条边。

采用数学归纳法:

于是我们有下面的两个推论:

总结

本文是对 Algorithms on Graphs 第3-4周 课程的一个记录,笔记更多的是给自己复习时快速查阅用。

你的鼓励是我继续写下去的动力,期待我们共同进步。
这个时代,每个人都是超级个体!关注我,一起成长!

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注