Namely, for directed graphs, actually, we need to add an edge from j to i.

So at this point we assume that our graph is undirected.

Okay, so this way we fill in all the table.

We've replaced some of the plus infinities with actual values and now we graph.

And then what remains to be done is to return the actual result.

And the result in this case can be computed as follows, so

this is just the last line of our code.

So recall that our function c of ys,

it always computes as the length of some part.

Starts in a node 0, ends in a high and visited all the nodes.

So first of all, we need to reset all the nodes.

And the second thing is that we need to return back to the initial values.

So we check all the various t (i) where i ranges

through all possible values from 1 to n.

So i ranges through all possible n vertices of our cycle.

And here we use the set that contains all the elements.

We need a number which has 1 at every position, okay?

And to compute such a number, we just take 2 to the n and subtract 1.

This is exactly the number which has 1 at 0 position,

1 at first position, 1 at second position and so on.

So this is just a number whose binary representation is the following one, okay?

So we check all such values and for every such part,

we add just the last weight of the edge from 0 to i, okay?

So once again, this is a path, this is an optimal weight of a path that starts at 0,

visits all the nodes at the n and then at the node, I'm sorry,

and then we need to add one more edge going from i to 0.

And this is exactly what is done here at the last step, okay?

So this is the main message picture but

this just reflects the fact that this is a non trivial algorithm.

And also, its implementation here uses some non standard probably not so

standard tricks.

But let me finally summarize, so the running time of this algorithm is n

squared times 2 to the n because we actually have three nested loops.

The outer loop ranges through all sort of small s

going from 0 to 2 to the n minus 1.

So for this reason, we have 2 to the n term.

Then i ranges from one to n and j ranges from,

also from 0 to n, and that's why we have n squared term.

So it is my much better than factorial,

so n squared to the n grows slower than n factorial.

So sometimes this approach is better than range and bond, but sometimes range and

bond is better than dynamic programming.

So 2 to the n, and

this approach is definitely faster than going through all possible permutations

because going through all possible permutations is n factorial.

But still unfortunately, this approach is too slow already for n = 20.

Okay, so this approach just allows us to solve and practice instances

consisting of, say, 15 nodes depending on the actual implementation.

So while going through all permutations is too slow over the full 4 equal to 15,

this one is okay for n equal to, say, 15 or 14, okay?

So this is faster than n factorial, but for practical applications,

this is unfortunately still too slow.

So in practice, much more often, the branching bond

technique is used with some smart usage of heuristics.