4.4 Dijkstra’s algorithm Flashcards
1
Q
What is the length of a walk in an unweighted graph + what is the distance between 2 vertices
A
1
Q
What is a weighted graph
A
2
Q
What are negative weights in graphs
A
May or may not be ignored (think might be on ps)
3
Q
What is the idea behind Dikstra’s algorithm
A
BFS with weights (using priority queue). Explore all shortest paths first.
4
Q
Prove the following:
A
Know that d(x,y) + length(y,z) is more since was not picked first
5
Q
What is a priority queue
A
6
Q
What is the psuedo-code for Dijkstra’s algorithm
A
7
Q
What is the runtime of Dijkstra’s algorithm
A
