Dijkstra’s Algorithm.

Presentation on theme: "Dijkstra’s Algorithm."— Presentation transcript:

1 Dijkstra’s Algorithm

2 Correctness

3 Implement Q: How to do line 4 efficiently? d'(v) = mine = (u, v): u∈S {d(u)+le} A: Explicitly maintain d'(v) in the view of each unexplored node v instead of S Next node to explore = node with minimum d'(v). When exploring v, update d‘(w) for each outgoing (v, w), w ∉ S. Q: How? A: Implement a min priority queue nicely Opration Dijkstra Array Binary heap Fibonacci heap Insert O(n) Θ(lg n) Θ(1) ExtractMin O(lg n) ChangeKey O(m) O(1) IsEmpty Total O(n2) O(m lg n) O(m+n lg n) 对于演算法来说，效率非常重要。对于这个演算法来说，最主要的是在第四行，我们主要是要考虑怎样能快速找到d value加上edge weight是最小的。这个时候我们就需要一个很好的data structure，他可以把所有点上暂时的d’的值可以很快吐出最小值。那么他在这里做的时候呢，跟procedure的做法稍稍有点不同，原来procedure是以S的观点往外reach出去距离最近的人是谁，而真正在implementation的时候，我们把这个事情来换一个角度去看，我们把每个点身上随时都去记录一下目前我知道从source点出发到达这一点的最短距离。一开始我不知道是多少，我就设定它为无限大，然后在计算过程中不断下降直到最后达到最小值。所以这里我们就需要implement一个min priority queue（优先队列），每个点身上都有一个d value，所以我们就是把所有点都放到这个min priority queue里面，那一开始所有人的d value都是无限大，在运算过程中都会往下降，

4 Example 下面看个例子，让大家感受下在implementation上面，Dijkstra是怎么做的。一开始的时候把所有点都maintain在一个min priority queue里面，然后利用ExtraMin每次都可以把最小值吐出来去掉，一开始从s开始做，把s的最小值吐出来之后，接下来ExtraMin透过s更新其他点的d value，他explore点的顺序是按照d value递增的顺序。

5 Recap Heaps: Priority Queues
Binary Tree Application 接下来就是复习Priority Queue的implementation。Priority Queue有两种形式，一种是以最小值为优先，一种是以最大值为极端。这边为了要介绍sorting，所以会介绍Max Priority Queue。

6 Priority Queue In a priority queue (PQ)
Each element has a priority (key) Only the element with highest (or lowest) priority can be deleted Max priority queue, or min priority queue An element with arbitrary priority can be inserted into the queue at any time The time complexities are worst-case time for binary heap, and amortized time complexity for Fibonacci heap Operation Binary heap Fibonacci heap FindMin Θ(1) ExtractMin Θ(lg n) Insert ChangeKey Priority Queue的特性就是每笔data身上都伴随着一个key value，key value的多寡就可以表达priority的高低。Key val越大，Priority越高的叫Max priority queue，值越低，Priority越高的叫Min priority queue。Dijkstra Algorithm用的就是Min priority queue，但是这边介绍的是Max priority queue。对于一个priority queue，我们想要对它做的动作有以下几种。这边列举了min priority queue的几个operation。第一个是想要找到priority最高的人，就是FindMin，第二个就是找到priority最高的并且remove它，remove掉之后我还希望剩下来的还能维持priority queue的形式，第三个就是insert一个新的值，第四个就是改变一个key value。

7 Heap Definition: A max (min) heap is
A max (min) tree: key[parent] >= (<=) key[children] A complete binary tree Corollary: Who has the largest (smallest) key in a max (min) heap? Root! Example Heap这种data structure在概念上就是一种complete binary tree的形式。所谓complete就是上层都是塞得满满的，只有最后一层可能会有缺漏。 Corollary 推论

8 Class MaxHeap Implementation?
Complete binary tree → array representation 刚刚说到priority queue在概念上是用complete binary tree来建构，在implement的时候我们就是用array来建它。因为他是一个complete binary tree所以他的index是连续的。这边为了一一对应，所以舍弃0这一项

9 Insertion into a Max Heap (1/3)
Maintain heap property all the times Push(1) 一般在maintain一个heap的时候，我们会maintain两个东西，一个就是heapSize，表示当下有多少笔资料是维持heap的形式，一个就是capacity，他表示我一开始宣告这个array的长度。假设现在要insert一笔新的资料，它的key value是1.因为是一个complete binary tree所以要在2的尾巴这边insert不是在14或者10这边insert。Insert完了之后我们要来确认一下有没有违反大小顺序。

10 Insertion into a Max Heap (2/3)
Maintain heap → bubble up if needed! Push(21) 下面我们来insert一个21，我们发现insert之后，它并不满足Max heap的大小关系，所以接下来我们就要把它跟它的parent作交换，然后继续比较交换。

11 Insertion into a Max Heap (3/3)
Time complexity? How many times to bubble up in the worst case? Tree height: Θ(lg n) 这个时候的complexity是O(lg n)

12 Deletion from a Max Heap (1/3)
Maintain heap → trickle down if needed! Pop() 接下来就是remove的动作，对于一个heap来说，我肯定是remove priority最高的，对于max heap来说就是remove root，然后把排名最后的塞到root的位置，然后就是修正大小关系。在作交换的时候要和左右两个小孩先比较一下再做交换。

13 Deletion from a Max Heap (2/3)
Maintain heap → trickle down if needed! Pop() 那我们要考虑这个动作的complexity，remove root和把尾巴移到root都只需要O(one),那再做重新排序的时候，最差可能就是把它交换到leaf端，所以会用O(lg n)

14 Deletion from a Max Heap (3/3)
Time complexity? How many times to trickle down in the worst case? Θ(lg n)

15 Max Heapify 接下来我们来看一个很重要的operation，叫Max Heapify，就是让data structure形成leap的形式。

16 How to Build a Max Heap? How to convert any complete binary tree to a max heap? Intuition: Max heapify in a bottom-up manner Induction basis: Leaves are already heaps Induction steps: Start at parents of leaves, work upward till root Time complexity: O(n lg n)