The main results of the paper are concerned with determining the optimal stationary strategies for stochastic discrete control problems on networks with discounted costs. We ground polynomial time algorithms for determining the optimal strategies of this problem using a linear programming approach. Additionally, we show that the proposed approach can be extended for Markov decision processes with a total discounted cost optimization criterion.