Dijkstra, A* and trees

Dijkstra, A* and trees

1. Dijkstra

   • Shortest path algorithm
     • The graph is agnostic, meaning it doesn't know how deep the tree goes or where all the nodes are.....
   • The graph doesn't have heuristics
   • The graph is weighted and these weights are called costs and are taken into account to find the optimal path
   • Finds the optimal path every time, but with a large graph, the time for this is execute is longer than A*
   • Used in packet switching to find the shortest, low cost route to send packages acorss a network.

2. Trees

   • Adding
     • Iterative approach
       • 3. Once the null is found then a new node in the tree is created, to the left of the previous node if smaller than parent node, to the right if not.
       • 2. This keeps happening until a null is found
       • 1. while the current node does not equal null (i.e we haven't fallen off of the tree yet) then compare the node to be inserted with the current node you are on, if it is bigger then transverse to the right if not then to the left.
     • Recursive approach
       • 1. Starting at the root, compare this to the node that is being inserted. 2. Traverse down the tree and continue this by recurse. 3. If you reach a leaf node, insert the node at the left if it is less than the current parent node or at the right if the node is larger than the current parent node.
     • Description
       • New nodes are always added at the leaf node, either to the left if it is smaller and to the right if it was greater than the current node.
     • WORST CASE SCENARIO ADDING A NODE TO A TREE IS TO TRAVERSE FROM THE ROOT TO THE DEEPEST LEAF. THIS MEANS THE TIME COMPLEXITY IS O(N)
   • Description
     • Trees are organised with a root, and everything to the left is smaller than the root, and everything to the right of the tree is larger than the root.
   • Subtracting
     • 1. Find the node you want to delete (you can use binary search for this as in a binary search tree the nodes are all in order. 2. Then, you promote either the left or the right branch to the level that the node you are deleting is currently on, and then 3. hang the remaining nodes to ensure they aren't going to be lost.

3. A*

   • Uses costs and heuristics to find the shortest path to a node.
   • There are three costs involved, the G cost, which is the normal weights along the lines of a graph.
   • The H cost which is the heuristic cost which is found by the node value.
   • The F cost which is the final cost by adding the G and H cost together. This cost is the one used to assess the next node to chose from the open set.