"Combinational" Decision Graph - Cheapest search algorithm
Your problem is $\mathcal{NP}$-hard, by reduction from $\mathcal{3SAT}$. Let $\Phi = \phi_1 \wedge \dots \wedge \phi_m$ be a CNF formula with variables $V = \{x_1, \dots x_n\}$. Let $\mathcal{L}(V)$ be the set of literals of $V$. Let joining nodes, decision nodes, cost nodes be defined as in your question.

For each $x_i$, we create four cost nodes $t_i$, $f_i$, both with cost $1$, representing an assignment of, respectively, true and false to $x_i$. Let $S$ be the set of all such nodes.

Let $\phi_i = \psi_{1i} \vee \psi_{2i} \vee \psi_{3i}$ be a clause with $\psi_{1i}, \psi_{2i}, \psi_{3i} \in \mathcal{L}(V)$. Without loss of generality, we may assume that $\psi_{1i}, \psi_{2i}, \psi_{3i}$ are literals obtained from different variables. Of the eight possible assignments of truth values to those variables, seven satisfy $\phi_i$. For each of those assignments, we create a joining node $c_{ki}$, which has as a successor every node $s \in S$ corresponding to the values relative to such assignment. For example, if the $k$-th assignment were "$x_\alpha$ true, $x_\beta$ false, $x_\gamma$ true", $c_{ki}$ would have $t_\alpha, f_\beta, t_\gamma$ as successors. Finally, we create a decision node $d_i$ with successors $c_{1i}, \dots, c_{7i}$ and let the starting node have as successors each of the $d_i$.

Now, observe that any solution path in the decision graph that we have built has weight at least $n$. In fact, whenever we encounter a fresh variable $x_i$, we are forced to take either $t_i$ or $f_i$, both of which have cost $1$. Furthermore, any path with cost not exactly $n$ has taken, by the pigeonhole principle, both $t_k$ and $f_k$ for some $k$, which means that it does not correspond to a consistent assignment of truth values to the variables of $V$.

On the other hand, an assignment of truth values to variables that satisfies $\Phi$ corresponds to a path of weight exactly $n$ (choose $t_i$ for every variable $x_i$ set to true, $f_i$ for every variable $x_i$ set to false, follow every arrow in the opposite direction).

We conclude that determining the optimal path is at least as hard as $\mathcal{3SAT}$, and consequently, as every problem in $\mathcal{NP}$.

As always with $\mathcal{NP}$-hard problems, your choice is to go with either heuristics or approximation schemes. If I may make a suggestion, problems like this are a good fit for logical programming tools, such as CSP/ASP.