Some path problems cannot be modeled using
semirings because the associated algebraic structure is not
distributive. Rather than attempting to compute globally optimal
paths with such structures, it may be sufficient in some cases
to find locally optimal paths—paths that represent a stable
local equilibrium. For example, this is the type of routing
system that has evolved to connect Internet Service Providers
(ISPs) where link weights implement bilateral commercial
relationships between them. Previous work has shown that
routing equilibria can be computed for some non-distributive
algebras using algorithms in the Bellman-Ford family. However,
no polynomial time bound was known for such algorithms. In
this paper, we show that routing equilibria can be computed
using Dijkstra’s algorithm for one class of non-distributive
structures. This provides the first polynomial time algorithm
for computing locally optimal solutions to path problems. We
discuss possible applications to Internet routing.