> To see why interior point methods are more efficient, suppose your feasible region is a convex n-gon in XY plane, for some very large n. The convex n-gon is

> To see why interior point methods are more efficient, suppose your feasible region is a convex n-gon in XY plane, for some very large n. The convex n-gon is a really bad counterexample since the encoding length for inequalities describing it is Omega(n) - thus the required number of simplex iterations is linear in the input length. Better consider the Goldfarb cube (Nina Amenta and Günter M. Ziegler: Deformed products and maximal shadows of polytopes, Contemporary Math. 233 (1999), 57-90.). > No. Dijkstra's algorithm operates on fundamentally discrete structures (finite graphs), whereas the simplex method solves linear programming problems with continuous variables (conceptually ranging over the reals, although of course on a computer one uses floating-points or some other approximate representation). It is equivalent to optimize over a finite set of points in Z^m or over its convex hull. The convex hull of the integer points in a rational polyhedron is a rational polyhedron again. So we just have to know its facet-defining inequalities. Sometimes these are known - for example for the problem of finding the shortest path with nonnegative edge weights (here the Total Unimodular (TU) property holds). Any step of the Dijkstra algorithms corresponds to some specific simplex iteration (or dual simplex iteration? - at least one of them). Yes, as an implementation it is faster to implement it on discrete data structures, but fundamentally it is a simplex algorithm in strong disguise. Source: I currently do my PhD in discrete optimization.