  The paper deals with finite-state Markov decision processes (MDPs) with
integer weights assigned to each state-action pair. New algorithms are
presented to classify end components according to their limiting behavior with
respect to the accumulated weights. These algorithms are used to provide
solutions for two types of fundamental problems for integer-weighted MDPs.
First, a polynomial-time algorithm for the classical stochastic shortest path
problem is presented, generalizing known results for special classes of
weighted MDPs. Second, qualitative probability constraints for weight-bounded
(repeated) reachability conditions are addressed. Among others, it is shown
that the problem to decide whether a disjunction of weight-bounded reachability
conditions holds almost surely under some scheduler belongs to $\textrm{NP}\cap
\textrm{coNP}$, is solvable in pseudo-polynomial time and is at least as hard
as solving two-player mean-payoff games, while the corresponding problem for
universal quantification over schedulers is solvable in polynomial time.
