Dijkstra’s Algorithm.

Slides:



Advertisements
Similar presentations
讀經教育  第一組:吳碧霞、陳鍾仁  第二組:吳雪華、謝濰萁  第三組:邱國峰、林佳玫. 不論上智下愚 成功的教育 讓每個孩子 都能成為最優秀的人才.
Advertisements

3 的倍数的特征 的倍数有 : 。 5 的倍数有 : 。 既是 2 的倍数又是 5 的倍数有 : 。 12 , 18 , 20 , 48 , 60 , 72 , , 25 , 60 ,
第四单元 100 以内数的认识
第四单元 100 以内数的认识
電腦與問題解決 5-1 電腦解題概論 5-2 電腦解題程序 5-3 演算法概論.
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
基本概論 Basic concepts.
算法分析(3) 重要的数据结构.
動畫與遊戲設計 Data structure and artificial intelligent
疯狂的励志 —献给渴望改变命运的有志者.
資料結構與C++程式設計進階 資料結構概論 講師:林業峻 CSIE, NTU 6/ 7, 2010.
你的潜能是无限的 ——高三心理辅导.
Minimum Spanning Trees
Large-Scale Malware Indexing Using Function-Call Graphs
§4 Additional Binary Tree Operations
Chap4 Tree.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
課程名稱:資料結構 授課老師:_____________
樹狀結構 陳怡芬 2018/11/16 北一女中資訊專題研究.
佇列 (Queue).
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
Chapter 6 Graph Chang Chi-Chung
The Greedy Method.
演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)(binary Searching、Quick Sort…. ) The Greedy Method(貪婪演算法) (Prim MST、Kruskal MST、Djikstra's algorithm) Dynamic.
Data Structure(資料結構) 授課老師: 蕭志明 助理教授 Ext:6779
第十五章 Linked List, Stack and Queue
计算机问题求解 – 论题 堆与堆排序 2018年05月14日 数据的组织(逻辑的,物理的)均可以影响到算法的设计和性能.
第十一章 Heap 結構.
组合逻辑3 Combinational Logic
圖表製作 集中指標 0628 統計學.
第 七 章 樹狀結構 課程名稱:資料結構 授課老師:________ 2019/1/1.
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.
Data Structure.
樹 2 Michael Tsai 2013/3/26.
2-3-4 Tree and how it relates to Red Black Tree
Advisor : Prof. Frank Y.S. Lin Presented by Yen-Yi, Hsu
感謝同學們在加分題建議. 我會好好研讀+反省~
B+ Tree.
使用矩阵表示 最小生成树算法.
Chapter 5 Recursion.
網路遊戲版 幸福農場168號.
資料結構 Data Structures Fall 2006, 95學年第一學期 Instructor : 陳宗正.
資料結構 優點 缺點 1 陣列 (Array) 沒有額外變量 (例head, next,...) 運作/操作較簡單 更新資料時,若要保持順序,需要移動較大量資料 靜態結構Static (宣告時已決定了陣列元素多少,不能在程式執行期間增減元素) 2 隊列Queue (FIFO) 容易更新 加入enqueue:
鄧姚文 資料結構 第一章:基本概念 鄧姚文
Total Review of Data Structures
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
第8章 資料排序 資料結構設計與C++程式應用
Linked Lists Prof. Michael Tsai 2013/3/12.
Hashing Michael Tsai 2013/06/04.
计算机问题求解 – 论题 算法方法 2016年11月28日.
均質化計畫形成 與 撰寫及執行經驗分享 光隆家商 楊瑞明
Amortized Analysis Michael Tsai 2013/11/14.
Disjoint Sets Michael Tsai 2013/05/14.
计算机问题求解 – 论题1-5 - 数据与数据结构 2018年10月16日.
最短通路问题.
唐常杰 四川大学计算机学院 计算机科学技术系
SLIQ:一种快速可伸缩分类器 Manish Mehta, Rakesh Agrawal, Jorma Rissanen IBM Almaden Research Center, 1996 报告人:郭新涛
Hashing Michael Tsai 2017/4/25.
5. Combinational Logic Analysis
世界无烟日主题班队会.
Module 9 Unit 2 Happy Birthday
怎樣把同一評估 給與在不同班級的學生 How to administer the Same assessment to students from Different classes and groups.
活動主題:能「合」才能「作」 指導教授:張景媛教授 設 計 者:協和國小團隊 李張鑫 × 陳志豪.
计算机问题求解 – 论题 基本的数据结构 2018年05月09日.
Data Structure.
Maximum Flow.
JAVA 程式設計與資料結構 第十七章 Tree.
第八章 大眾文化對消費者行為的影響 消費者心理學 徐達光著.
105-1 Data Structure Homework 4
Presentation transcript:

Dijkstra’s Algorithm

Correctness

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都是无限大,在运算过程中都会往下降,

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

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

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。

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 推论

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

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完了之后我们要来确认一下有没有违反大小顺序。

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

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)

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

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

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

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

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)