Activity

Here’s the Deal

Slant is written by a community helping you be informed. Tell us what you’re passionate about to get an awesome personalized feed.

3 Recommended Products | Recommendations | Price | Last Updated |
---|---|---|---|

#1 A* Algorithm· · · | 7 | 0 | – | Jun 3, 2017 |

#2 Dijkstra's Algorithm· · · | 4 | 0 | – | Dec 21, 2015 |

#3 Breadth-first search· · · | 0 | 0 | – | Sep 24, 2017 |

### Pro Heuristic

A* expands on a node only if it seems promising. It's only focus is to reach the goal node as quickly as possible from the current node, not to try and reach every other node.

### Pro Complete

A* is complete, which means that it will always find a solution if it exists.

### Pro Can be morphed into other algorithms

A* can be morphed into another path-finding algorithm by simply playing with the heuristics it uses and how it evaluates each node. This can be done to simulate Dijkstra, Best First Search, Breadth First Search and Depth First Search.

### Con Not useful if you have many target nodes

If you have many target nodes and you don't know which one is closest to the main one, A* is not very optimal. This is because it needs to be run several times (once per target node) in order to get to all of them.

### Pro Uninformed algorithm

Dijkstra is an uninformed algorithm. This means that it does not need to know the target node beforehand. For this reason it's optimal in cases where you don't have any prior knowledge of the graph when you cannot estimate the distance between each node and the target.

### Pro Good when you have multiple target nodes

Since Dijkstra picks edges with the smallest cost at each step it usually covers a large area of the graph. This is especially useful when you have multiple target nodes but you don't know which one is the closest.

### Con Fails for negative edge weights

If we take for example 3 Nodes (A, B and C) where they form an undirected graph with edges: AB = 3, AC = 4, BC=-2, the optimal path from A to C costs 1 and the optimal path from A to B costs 2. If we apply Dijkstra's algorithm: starting from A it will first examine B because it is the closest n...

### Pro Complete

BFS is complete, which means that it will always find a solution if it exists.

### Pro Optimal for finding the shortest path in a graph

BFS is very useful when you want to find the shortest and most optimal path by traversing as few edges as possible.

### Con Requires a large amount of memory

When traversing one tree level, you need a way to know which nodes to traverse once you get to the next one. The way this is done is by storing the pointers to a level's child nodes while searching it. The pointers are stored in a FIFO way, this means that BFS needs a relatively large amount of...

### Comments

Welcome to the Slant Community

Stop spending hours researching

Slant is written by a community helping you be informed. Let us know what you’re passionate about to get an awesome personalized feed.