1) Shortest Corcuit Problems

Question 1

What even is a shortest circuit problem

Answer 1

Problem is to find the shorter part to get from one place to the other, taking into consideration the length (weight) of the paths

Question 2

How do we assign if we go through one path or not

Answer 2

First going from A to B = AB , B to a = BA

Going down AB means I assign a 1 to Ab. Not going down BA means assigning a 0

This way, whatever path we get at the end, multiplying the weight by 1 will give the weight

Question 3

How to start the LP

Answer 3

Of course we have to MINIMISE

And we are basically minimising the lentgh needed

=== thus we need an equation for the TOTAL LENGTH OF THE CIRCUIT

Question 4

How to find the total length of the circuit?

What makes a length possible

Answer 4

Basically it’s the sum of
- multiply thr weight by the variable name so like 8AB
- now add ALL THE LENTGHS (yes even if you’d never go back) POSSIBLE

A possible length is everything except paths going BACK TO THE START, or AWAY FROM THE END

Question 5

Again what makes a path “possible” as you call it

Answer 5

any path going to and from the corner is possible , except going back TO THE ORIGINAL POINT , and anything going AWAY FROM THE ORIGINAL POINT

Question 6

Okay what about cinstraints

Answer 6

Here you want to check each corner by corner and make a separate contrarian for each

• for the start = each path going out = 1
• for the end = each path going in = 1

For any other = paths going out - paths going in = 0

(EXCLUDING PATHS GOING AWAY FROM END OR TO BEGINNING)

Question 7

Explain the cinstraints

Answer 7

For start and end, this is because you are only going to choose one while the rest are zero so they sum to 1

For in between , you either don’t go through that vertex if it’s not shortest path, in which case everyhting is 0

Or

One path is picked going through and thus one path picked going out, so 1-1 = will always be 0