This paper develops an algorithm for finding the dynamic shortest path from the
source node to the sink node in stochastic dynamic networks, in which the arc lengths are
independent random variables with exponential distributions. In each node there is an
environmental variable, which evolves in accordance with a continuous time Markov process.
The parameter of the exponential distribution of the transition time of each arc is also a
function of the state of the environmental variable of its initiating node. It is also assumed
that upon arriving at each node, we know the state of its environmental variable and also the
states of the environmental variables of its adjacent nodes. Upon arriving at each node, we
can move toward the sink node through the best outgoing arc or wait for encountering the
better state of its environmental variable, which reduces the expected transition times of the
outgoing arcs. In this paper, we apply the stochastic dynamic programming for finding the
dynamic shortest path from the source node to the sink node by obtaining the optimal strategy
of movement in each node of the network.