Graphs (Undirected with Weights) Flashcards
What does Dijkstra’s algorithm do?
It finds the shortest path. Uses a priority queue.
It doesn’t touch every node. Just uses pathfinding to find whatever path is cheapest.
What is Dijkstra’s algorithm an example of?
It is an example of a greedy algorithm because it always tries to use the next cheapest cost.
What happens when a node is visited in Dijkstra’s algorithm?
When a node is visited, it is put in the queue. It adds the total cost on how to get to it. If a total cost which is cheaper is found later, the initial node value will be replaced with the cheaper node value.
What is the goal of Dijkstra’s algorithm?
It prioritizes the cheapest way to get to the goal destination. The cheapest way depends on the parent. As we discover a cheaper way, we throw out an older way so by the time we get to the destination, that is the final cheapest way to get there.
