AQA Paper 1 - Fundamentals of algorithms

Graph Traversal & Dijkstra

• Breadth-First searches are effectively visiting the top node, queueing the next unsearched adjacent nodes and then searching those nodes and adding to the queue next unsearched adjacent nodes until the whole graph has been visited
• Depth-First searches are going as deep as possible into one mode then backtracking and trying a different one until the whole graph has been visited

• Remember the dot placement for pre-order, post-order and in-order on the diagram in the classroom

• Dijkstra's shortest path algorithm finds the shortest path by setting the value of all nodes to infinity, then reducing them to slowly…