Re:Linear Programming: How Does It Work?
by arghbleargh on Monday June 06, 2016 @04:31AM
(#11845375)
There is a linear programming formulation of the shortest path problem: see https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear.... Indeed the vertices of the simplex method would correspond to paths, but I think running the simplex method on the dual formulation is more akin to Dijkstra's algorithm. Actually, I think the simplex method on the dual and Dijkstra's are equivalent, although I did not work through the details carefully.
[ Parent
| on HN ]
Re:Linear Programming: How Does It Work?
by mathgenius on Monday June 06, 2016 @11:24AM
(#11847437)
Aha, yes, this is what I was looking for. Thankyou!
Reminds me also of using linear programming to do belief propagation and decode sparse codes.