Shortest Path Algorithm

It is only for reviewing, not for learning.
-----------------------------------------------
-----------------------------------------------
Algorithm 1: DIJKSTRA(G, w, s)
Greedy Algorithm
1: Overlapping subproblems
2: Optimal substructure
3: Greedy-choice property
-----------------------------------------------
-----------------------------------------------

----------------------------------------------
Cost:

--------------------------------------------- 
Notes:
1) DIJKSTRA is a type of BFS (Breadth-First-Search).
2) If each edge has the same cost, the algorithm can be improved by using FIFO queue instead of heap and get O(V+E).
Nature:
Smaller weights edge always pushed in the queue earlier. Or
v comes after u in Q implies that d[v] = d[u] or d[v] = d[u] + 1.



-----------------------------------------------
-----------------------------------------------
Algorithm 2: DFS
-----------------------------------------------
----------------------------------------------- Recursive Algorithm

DFS(Node) {
     Color(Node);
     Loop (n in Adjacent Nodes) {
           DFS(n);
     }
}

Non-Recursive Algorithm (Using LIFO Stack)

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.first();  // nodes_to_visit is a LIFO stack
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

-----------------------------------------------
-----------------------------------------------
Algorithm 3: BFS
-----------------------------------------------
-----------------------------------------------
Non-Recursive Algorithm (Using FIFO Queue)

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.first();  // nodes_to_visit is a FIFO queue
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

Recursive Algorithm // surprisingly, it is not that easy as DFS.

BFS(Queue) {
     if(Queue is empty) return;
     Queue.pop();
     //do something
     Queue.push(Children);
     BFS(Queue);
}

-----------------------------------------------
-----------------------------------------------
Algorithm 4: A* Algorithm
-----------------------------------------------
-----------------------------------------------
1) DIJKSTRA uses local optimal in the greedy algorithm. However, local optimal is not a good enough choice in many many cases.
2) A* Algorithm uses estimated global optimal in the greedy algorithm.
How to estimate? That's the MAGIC.

It uses a knowledge-plus-heuristic cost function of node x (usually denoted f(x)) to determine the order in which the search visits nodes in the tree.

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal.It is a very string requirement, since the true cost is unknown.

But it does exist in many cases. And, h(x) part of the f(x) function must be very near to the distance to the goal. Otherwise, it does not help much on the algorithm efficiency.

An example of an A star (A*) algorithm in action where nodes are cities connected with roads and h(x) is the straight-line distance to target point.

The contribution of A* Algorithm is that:
A* Algorithm gives a different type of algorithm design methodology, which can be used to make searching more efficient, if localized searching is much worse than optimal.

The time complexity of A* depends on the heuristic. The big-O time complexity may be the same with DIJKSTRA. But the number of checking nodes can be much smaller.

                                      DIJKSTRA Algorithm Search Space

                                                 A* Algorithm Search Space