Compute by hand the lowest possible cost for traversing the graph in Figure XXXXXXXXXXusing the dynamic programming method. MAP inference in chain models can also be performed by running Djikstra’s...

Compute by hand the lowest possible cost for traversing the graph in Figure 11.22 using the dynamic programming method.

MAP inference in chain models can also be performed by running Djikstra’s algorithm on the graph in Figure 11.23, starting from the node on the left-hand side and terminating when we first reach the node on the right-hand side. If there are

N

variables, each of which takes

K



values, what is the best and worst case complexity of the algorithm? Describe a situation where Djikstra’s algorithm outperforms dynamic programming.