Using Python programming

Implement Dijkstras algorithm to find the shortest paths in a graph.

Implement two versions of a priority queue class, one using an unsorted array (a python list) as the data structure and one using a heap. For the array implementation, insert and decrease-key are simple O(1) operations, but delete-min will unavoidably be O(|V|). For the heap implementation, all three operations (insert, delete-min, and decrease-key) should be worst-case O(log|V|). For your binary heap implementation, you may implement the binary heap with an array, but also remember that decrease-key will be O(|V|) unless you have a separate array (or map) of object references into your binary heap, so that you can have fast access to an arbitrary node. Also, don't forget that you will need to adjust this lookup array/map of references every time you swap elements in the heap. (This was not discussed in detail in class, but you can figure it out.)

1. Just to be clear, you may NOT use an existing heap implementation. You must implement both versions of the priority queue from scratch.