A→B is 4, A→C is 1, C→B is 2. What is the shortest distance from A to B?
- Direct A→B: 4.
- Via C: 1 + 2 = 3.
- Shortest is 3.
Answer 3
A-level Computer Science revision · Data structures and algorithms
Dijkstra's algorithm finds the shortest path from a start node to all others in a weighted graph with non-negative weights. It repeatedly visits the unvisited node with the smallest known distance and updates its neighbours. A* adds a heuristic estimate of the distance to the goal, so it explores fewer nodes towards a single target.
Watch out A* is only guaranteed to find the shortest path if the heuristic never overestimates.
A→B is 4, A→C is 1, C→B is 2. What is the shortest distance from A to B?
Answer 3
A→B 7, A→C 3, C→D 2, D→B 1, C→B 5. What is the shortest distance from A to B?
How does A* differ from Dijkstra's algorithm?
Dijkstra's algorithm does not work correctly with:
A-level Computer Science Pro, OCR H446
£119 once
Price rises to £199 on 1 January. Save £80 by joining before then.
At least 12 months of access
No VAT is charged.