CISC 365 Lecture Notes - Lecture 2: Brie, Fibonacci Heap
25 Sep 2016
School
Department
Course
Professor
Document Summary
To everyone"s amusement, we spent much of the lecture time locked in combat with the av equipment. We did manage to trace through the execution of dijkstra"s algorithm on a small example. We brie y discussed the computational complexity of the algorithm. What follows here is a more in-depth analysis: Assume the graph has n vertices and m edges. Select the vertex in c with the least b() value. Examine all neighbours of the selected vertex potentially performing some update work on each one. If c is stored in an array, choosing the vertex with the least b() value takes. Alternatively, if c is stored in a min-heap, choosing the vertex with the least b(v) value and repairing the heap takes o(log n) time. If c is stored in an array, the update work for each neighbour takes o(1) time.
