A-Level Computer Science – Dijkstra’s, A* & Travelling Salesman Explained (OCR / AQA) | S12:Ep6*

<p>This episode introduces <strong>optimization algorithms</strong> in computer science, specifically focusing on <strong>Dijkstra's shortest path algorithm</strong> and the <em>A algorithm</em>*. It explains how Dijkstra's algorithm finds the shortest path between a starting point and all other nodes in a <strong>weighted graph</strong>, with applications in areas like internet routing and GPS. The document then contrasts computable and incomputable problems, using the <strong>Travelling Salesman Problem (TSP)</strong> as an example of an <strong>intractable problem</strong> that is difficult to solve efficiently. Finally, it introduces <strong>heuristic methods</strong> as a practical approach for finding approximate solutions to intractable problems, and describes the A* algorithm as a path-finding algorithm that uses a <strong>heuristic function</strong> to focus on reaching a specific goal node.</p>