Use a HEAP for the PQ itself, allowing Insert and Delete to be time Theta(lg v)

Have an additional indexing array to locate the vertices in the heap, enabling Update to also be time Theta(lg v)

Thus, assuming the graph is connected, the overall run-time is Theta(e(lg v)) for an adjacency list

PFS

What about an adjacency matrix?

We don't need a heap for the PQ in this case

Instead traverse the val[] array at each step to find the best edge

Since it takes Theta(v) to traverse the row of the matrix to find the neighbors of the current vertex, an extra V to find the best vertex to pick next does not add any extra asymptotic time

Thus, the overall run-time is the same as for BFS – Theta(v2)

How do they compare?

elgv vs v2

Depending upon how e relates to v, one may be preferable -- see notes from board

Shortest Path

Djikstra's Shortest Path algorithm

Can be implemented using the SAME PFS that we just discussed for MST

The only difference is the measure used for the priority

With MST, we wanted the smallest overall weight

For each vertex we wanted the smallest edge that could connect it to the tree

With SP, we want the smallest weight PATH from the starting vertex to each other vertex