Dijkstra's shortest path Flashcards
What is the purpose of Dijkstra’s shortest path algorithm?
To find the shortest path between a particular start node and every other node in a weighted graph.
Why type of graph does the Dijkstra’s work on and what do they consist of?
Undirected, weighted graphs that consist of nodes (circles) and edges (lines)
What does a weighted graph mean?
The edges have values along them, known as costs
What is known as the best way to get from one node to another?
It’s known as the least cost method
How is the cost of a path calculated?
It’s calculated by adding up all the individual weights on the edges that make up the path.
Give examples of what Dijkstra’s algorithm can be used for.
Can be used:
- to manage networks
- to control the movement of adversaries in video games
- gps navigation system, to calculate quickest route to take
What is the shortest path?
The shortest path is the sequence of nodes, in the order they are visited, which results in the minimum cost to travel between the start and end node.
What happens when the Dijkstra’s algorithm has finished running?
it produces a list that holds the following information for each node:
- The node label
- The cost of the shortest path to that node (from the start node)
- The label of the previous node in the path
Why does the algorithm start by initialising the costs of all of the nodes to infinity?
- To show that the cost has not yet been calculated.
- The costs are updated as shorter paths are found.
What is step one of the carrying out the Dijkstra’s algorithm?
- In the node column, list all of the nodes, starting with the start node
- In the cost column write an infinity symbol (for each node).
- In the previous column write none (for each node).
set the cost of the start node (A) to 0,0; there is no cost for A, as this is where you start from. - Create visited list, with headings: Node, Cost (from start), Previous.
What is step two of the carrying out the Dijkstra’s algorithm?
- Start with node that has the lowest cost in unvisited list. A is currently the lowest cost in the unvisited list; all other nodes have a cost of infinity. A becomes the current node.
- Examine the nodes that can be reached directly from A (A’s neighbours) that have not yet been visited:
- For example: The edge from A to B has a cost of 8. The cost currently recorded in your unvisited list is infinity. A cost of 8 is less than infinity, so you erase that and write 8 instead, and record the previous node as A.
- Once you’ve evaluated the cost for all of the neighbours of the current node, remove A from the unvisited list and add it to the visited list with its cost (0,0) and previous node (none).
What algorithm does Dijkstra’s algorithm use?
It’s similar to a breadth-first algorithm but it uses a priority queue rather than a FIFO queue
What could the cost represent on a weighted graph?
Distance, time taken or the cost of travel
