Finding the shortest path using linear programming
Channel: Ankit Singla
Date: 2021-03-25

I discuss one of the two standard formulations of the shortest path problem as a linear program. There is a counter-intuitive aspect, which I explain using a physical ball and string model. 

Sources: The linear program and physical model are rather well known at least to people in the CS theory and networking disciplines, but I don't know of the "canonical" source. If you do, I would be really happy to learn and point to it. The specific (larger) graph I used in my example is the same one as in the slides by Amir Ali Ahmadi at Princeton (see slide 10 here -- http://slideplayer.com/slide/8950051/) but beyond the graph structure, the work is my own.