What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting?

Lets, say we have a problem X. What should be the pre-conditions that we check in problem X definition that would allow us to formulate it as a SSSP.

Initial Idea for solution: I believe if it satisfies the property of optimal substructure. One can formulate the problem as SSSP as well.

  • $\begingroup$ Your question is incredibly broad. 1) What do you mean by "solved in a single SSSPP setting"? Surely you'd allow some reduction, but of which power? 2) What do you mean by "optimal substructure"? $\endgroup$
    – Raphael
    Jun 21 '16 at 9:00

Wonderful question!

In spite of the question been very general, this is indeed a research topic by itself. I will rephrase slightly the question as follows: "what are the conditions that enable the applicability of Dijkstra and/or A$^*$ to solve a problem?" Obviously, for those cases that could be identified, the translation you mention to a single-source shortest path comes from the fact that either Dijkstra or A$^*$ (if a heuristic function is available) can solve the problem.

As a matter of fact, your initial guess, optimal substructure is not far from the real answer. As others might not know this concept, let me please introduce a related concept to that:

Definition (Prefix Optimality) A solution path $\pi=\langle s, v_1, v_2, \ldots v_k\rangle$ is prefix-optimal if each of its prefixes is an optimal solution to the corresponding partial problem.

This definition is a specialized version of optimal substructure for the path-finding problem.

This said, the answer to your problem are Cost Algebras. Cost algebras propose a general notion of costs under which various search algorithms can be reformulated. More recently, an abstract formalism based on cost algebras has been introduced for costs suited for heuristic search algorithms such as A$^*$. See Stefan Edelkamp, Shahid Jabbar and Alberto Lluch Lafuente. Cost-Algebraic Heuristic Search. American Association for Artificial Intelligence, 2005, 1362-1367.

Definition (Monoid) Let $A$ be a set and $\times : A\times A\rightarrow A$ be a binary operator. A monoid is a tuple $(A, \times, \mathbf{1})$, if $\mathbf{1}\in A$ and for all $a,b,c\in A$: (1) $a\times b\in A$; (2) $a\times (b\times c)= (a\times b)\times c$; (3) $a\times\mathbf{1}=\mathbf{1}\times a=a$.

We have a set, and an operation defined over the elements of our set. Let us now define a total order over them:

Definition (Total order) Let $A$ be a set. A relation $\preceq\in A\times A$ is a total order whenever for all $a,b,c\in A$: (1) $a\preceq a$; (2) $a\preceq b \wedge b\preceq a\Rightarrow a=b$; (3) $a\preceq b\wedge b\preceq c\Rightarrow a\preceq c$; (4) $a\preceq b\vee b\preceq a$.

Additionally, the least and greatest operations, denoted as $\sqcup$ and $\sqcap$ respectively, are defined as follows: $\sqcup A=c$ such that $c\preceq a, \forall a\in A$ and $\sqcap A=c$ such that $a\preceq c, \forall a\in A$. A set $A$ is isotone if $a\preceq b$ implies both $a\times c\preceq b\times c$ and $c\times a\preceq c\times b$, $\forall a, b, c\in A$.

With all these elements we can finally introduce Cost Algebras:

Definition (Cost Algebra) A cost algebra $\mathcal{A}$ is defined as a 6-tuple $\langle A, \sqcup, \times, \preceq, \mathbf{0}, \mathbf{1} \rangle$, such that:

  • $\langle A, \times, \mathbf{1} \rangle$ is a monoid
  • $\preceq$ is a total order induced by $\sqcup$
  • $\mathbf{0}=\sqcap A$
  • $\mathbf{1}=\sqcup A$
  • $A$ is isotone

Now, any problem whose formulation satisfies the defintion of a Cost Algebra, can be solved with Dijkstra and/or A$^*$. The following are instances of cost algebras given by the authors:

  • $\langle \{\top, \bot\}, \vee, \wedge, \Rightarrow, \bot, \top \rangle$ (boolean): Network service availability

  • $\langle \mathbb{R}^+\cup \{+\infty\}, \min, +, \leq, +\infty, 0\rangle$ (optimization): Price, propagation delay

  • $\langle \mathbb{R}^+\cup \{+\infty\}, \max, \min, \geq, 0, +\infty\rangle$ (max/min): Bandwidth

  • $\langle [0,1], \min, \cdot, \geq, 0, 1\rangle$ (probabilistic): Performance and rates

  • $\langle [0,1], \max, \min, \geq, 0, 1\rangle$ (fuzzy): Performance and rates

Just a minute! What about your initial guess? Well, the authors proved that Cost Algebras actually imply prefix optimality (and hence, optimal substructure) so that their answer is more general than just saying that the problem has to verify the latter. As a matter of fact, Cost Algebras are verifiable whereas optimal substructure can not be immediately decided.

Hope this helps,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.