Let $G$ be a Cartesian product of two arbitrary directed weighted graphs $M$ and $N$. The weights are from a non-commutative finite idempotent semiring.
Do there exist advanced results on the single source shortest path (SSSP) problem for $G$? Suppose that $|V_M| = |V_N| = n$. Is it possible to solve SSSP in $\widetilde{O}(BMM(n))$?
