Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Dijkstra's + A*
1.3.1
| Question | Answer |
|---|---|
| Dijkstra's | Finds the shortest path between one node and all other nodes on a weighted graph A type of breadth-first search It doesn’t work for edges with a negative weight value If there is more than one shortest path, only one will be outputted |
| Dijkstra's in English (to calculate the shortest path) | 1set initial dist-from-start for all vertices 2each vertex: afind unvisited vertex closest to start bfor unvisited connected vertex: iCalc dist from start iiIf i < dist: 11Shortest distance = new distance 12Previous vertex = current + visited |
| Dijkstra's in English (to output the shortest path) | 4. Start from a goal vertex 5. Add the previous vertex to the start of a list 6. Repeat from step 5 until the start vertex is reached 7. Output the list |
| Dijkstra's in pseudocode (don't need to learn, just be able to trace and recognise) | |
| A* | Finds shortest path between vertices Weighted graph Nodes pruned Optimal path followed Heuristic estimates cost between next vertex + goal then follows path Best-first search Needs graph + heuristic data Doesn’t stop at first path |
| pruned (A*) | never searched |
| If heuristic overestimates (A*) | may not work |
| Heuristic data (A*) | estimate of the remaining distance to the goal after we move from one vertex to another |
| dijkstra refinement | A* |
| If heuristic underestimates (A*) | takes longer |
| A* in english (To calculate the shortest path between two nodes) | 1Set initial g+f for all nodes 2Until visited goal aPick unvisited node w/ lowest f bFor each unvisited connected node ig=edge+current edge iiIf i < f: 1connected node f value = newly calculated distance 2previous = current node + current |
| A* in english (To output the shortest path) | 3. Start from a goal vertex 4. Add the previous vertex to the start of a list 5. Repeat from step 4 until the start vertex is reached 6. Output the list |
| G (A*) | shortest distance from start |
| H (A*) | heuristic |
| F (A*) | G+H |
| A* in pseudocode (don't need to learn, just be able to trace and recognise) |
Created by:
FlashCardFun!