Summary: In {\it Imreh, B.} [Acta Cyb. 15, 327-338 (2002; Zbl 1012.68004)], a procedure is given for solving modified Process Network Synthesis problems. The idea of this procedure is that for every instance of the modified problem, an automaton can be defined such that an optimal solution can be found by performing a shortest path method in the weighted transition graph of this automaton. Here, we recall this algorithm and improve its efficiency by generating only a part of the transition graph and computing a required shortest path simultaneously.