4.4 Dijkstra’s algorithm

Question 1

What is the length of a walk in an unweighted graph + what is the distance between 2 vertices

Answer 1

Question 1

What is a weighted graph

Answer 1

Question 2

What are negative weights in graphs

Answer 2

May or may not be ignored (think might be on ps)

Question 3

What is the idea behind Dikstra’s algorithm

Answer 3

BFS with weights (using priority queue). Explore all shortest paths first.

Question 4

Prove the following:

Answer 4

Know that d(x,y) + length(y,z) is more since was not picked first

Question 5

What is a priority queue

Answer 5

Question 6

What is the psuedo-code for Dijkstra’s algorithm

Answer 6

Question 7

What is the runtime of Dijkstra’s algorithm

Answer 7