Motivação para o desenvolvimento de algoritmos simplex de caminho mais curto

Estou lendo os Algoritmos Simplex de Caminho Mais Curto Eficiente de Donald Goldfarb, Jianxiu Hao e Shen-Roan Kai que consideraram "a especialização do algoritmo simplex primitivo para o problema de encontrar uma árvore de caminhos mais curtos direcionados de um determinado nó para todos os outros nós em" uma rede de n nós ou localizando um ciclo direcionado de comprimento negativo.Algumas variantes eficientes desse algoritmo simplex de caminho mais curto são analisadas e demonstram exigir no máximo pivôs e O ( n 3 ) Tempo."$(n − 1)(n − 2)/2$$O(n^3)$

Estou tentando encontrar motivação para este artigo e me pergunto: o algoritmo Bellman-Ford não é bom o suficiente? Funciona em tempo, o que é bom para o tipo de gráfico com o qual o problema acima do algoritmo lida.$O(nm)$

Um grande problema em aberto na programação matemática é projetar um algoritmo de programação linear de tempo fortemente polinomial. Um problema relacionado é se alguma variante do algoritmo simplex é executada em tempo fortemente polinomial. Faz sentido primeiro provar fortes limites de tempo polinomial para variantes de simplex aplicadas a problemas para os quais já sabemos que existem algoritmos de tempo polinomial forte.