Fundamentals of algorithms (dijkstra's)

Question 1

What do optimisation algorithms do?

Answer 1

• Find the best possible solution to a problem

Question 2

Dijkstra’s algorithm: what does it do, examples

Answer 2

Dijkstra’s algorithm finds the shortest path from a starting node to every other node

• keeps track of visited nodes with a priortity queue
  |
• Used in satellite navigation systems to find the shortest route between locations
• Used in routers to send packets via the fastest route through a network

Question 3

Dijkstra’s algorithm: How does it work?

Answer 3

1. Select start and end nodes
2. Make note of distances of nodes from the start position. (Only the nodes connected to start will have a value, all others have a value of infinity)
3. Note the start node as fully explored. Choose the node cloest to start node, update the table to reflect shortest distance from A to each node. Mark that node as fully explored
4. Repeat step 3, continue until each node has been fully explored (and hence each edge)