CMPT 225 Lecture Notes - Hash Table, Adjacency List, Linear Search

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

Cost of dijkstra"s depends both on size of edge list and size of vertex list. More than one variable contributes to running time. Also very dependent on data structure used to store priority queue e = # edges v = # vertices. Indexed heap (heap with an associated hash table) Build heap by hand, make start vertex root, but everything else has same value (priority) so we don"t care where it goes. For indexed, same thing but also have to build hash table - holds heap"s vertex for each index (can use an array if you know they"ll be nice and simple) c is constant. Initialization o(v) | 2 x o(v), so o(v) Remove vertex o(log v) *v | o(log v + log v * c)*v