Target: From a node, find the shortest path through each level (N levels) towards the final node. Each level has many nodes (up to D) and the connections between nodes in neighboring levels have different weights.

# Exhaustive search

Finding all possible path to get the ideal path

Con: computation expenses

# A* search algorithm

Only find the best path in each step, a best-first search algorithm. Best is defined as F = the cost from start moving to current G +  heuristics (guessing the distance cost, might not be accurate) from current to end point H. G is the aggregated weight during each step, H can be the Manhattan distance to end point. 

https://blog.csdn.net/hitwhylz/article/details/23089415

Pro: fast

Con: non-optimal, stores all generated nodes in memory.

Dijkstra algorithm is when H=0

# Beam search

Only save a fixed number (called Beam Width) of best pathes at each level. Only those paths are expanded to next level.

Pro and Con: tradeoff between calculation and possibility of finding the optimal path

# Viterbi

Each step record the best path to each node till this level, and forget all other worse paths in future steps. The underlying assumption is if this best path cannot allow this path to be the global optimal, there is no possibility for other worse paths.

Pro: Accurate

Con: Calculation. O(N*D^2)

# Bellman–Ford algorithm

Record min distance for each vertice in d(u). Iterate through vertice and edge to allow d(u) getting closer to best solution.

Iterative N times (verice number), update each edge (u,v) with weight w, if d(u)+w has shorter distance d(v), update d(v) to d(u)+w

Iterate N times to ensure the longest path is updated. Not necessarily needed, can check whether any d(v) change in a whole iteration as a signal for early stop.

Need to check negative weight loop! If d(v) still changes after N iteration, must have negative loop.

Pro: Can find path with negative weight

Con: Time complexity. O(|V| |E|) vertice number and edge number