# Dijkstra's shortest path Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is the purpose of Dijkstra’s shortest path algorithm?

A

To find the shortest path between a particular start node and every other node in a weighted graph.

2
Q

Why type of graph does the Dijkstra’s work on and what do they consist of?

A

Undirected, weighted graphs that consist of nodes (circles) and edges (lines)

3
Q

What does a weighted graph mean?

A

The edges have values along them, known as costs

4
Q

What is known as the best way to get from one node to another?

A

It’s known as the least cost method

5
Q

How is the cost of a path calculated?

A

It’s calculated by adding up all the individual weights on the edges that make up the path.

6
Q

Give examples of what Dijkstra’s algorithm can be used for.

A

Can be used:

• to manage networks
• to control the movement of adversaries in video games
• gps navigation system, to calculate quickest route to take
7
Q

What is the shortest path?

A

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.

8
Q

What happens when the Dijkstra’s algorithm has finished running?

A

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
9
Q

Why does the algorithm start by initialising the costs of all of the nodes to infinity?

A
• To show that the cost has not yet been calculated.

- The costs are updated as shorter paths are found.

10
Q

What is step one of the carrying out the Dijkstra’s algorithm?

A
• 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.
11
Q

What is step two of the carrying out the Dijkstra’s algorithm?

A
• 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).
12
Q

What algorithm does Dijkstra’s algorithm use?

A

It’s similar to a breadth-first algorithm but it uses a priority queue rather than a FIFO queue

13
Q

What could the cost represent on a weighted graph?

A

Distance, time taken or the cost of travel