Week 11 Notes: Priority Queue Optimization to Prim's / Dijkstra's

[varmichelle]

• Priority queue sorts in increasing or decreasing order
• To flip you can either write a comparison function or negate the distances
• Priority queue speeds up prim's and dijkstra's when picking the minimum edge / vertex

Example implementation:
graph[N][N]
dist[N] = INF
dist[root] = 0
while q ! empty
k = q.top().index
w = q.top().distance
visited[k] = true
for j from 1 to graph[k].size()
v = graph[k][j].vertex
if (dist[v] > graph[k][k].distance && !visited[v])
dist[v] = graph[k][j].distance
q.push(v,dist[v] or -dist[v] depending on inc/dec sort order)

for dijkstra's:
if (dist[v] > graph[k][j] + dist[j]) then update