Proof that there is a shortest path between two specific nodes in a weighted, connected digraph which has no negative cycles Let $G=(V,E,W)$ is a directed graph, where $V$ and $E$ are the sets of nodes and edges, respectively, while $W: E \rightarrow \mathbb{R}$ is an arbitrary weight function. How to prove that there exists a shortest path from an $s \in V$ to a $t \in V$ if and only if $G$ does not contain negative-cost cycles.
The shortest path from $s$ to $t$ is the path $e_1,e_2,...,e_n$ for which $\sum W(e_i)$ is minimal.
I am sure that this is a very elementary proof, but I did not found it directly.
 A: Some thoughts that may be too long for a comment: assuming the length of a path $e_1 \ldots e_n$ to be $W(e_1) + \cdots + W(e_n)$, fix $s,t \in V$ and consider $\mathcal P$ the set of (finite) and $\mathcal P_{s,t}$ the subset of paths from $s$ to $t$. We have a length function
$$
\ell \colon \mathcal P \to \Bbb R, \quad \ell(e_1\ldots e_n) = W(e_1) + \cdots + W(e_n)
$$
which is compatible with path concatenation, that is $\ell(\omega\omega') = \ell(\omega) + \ell(\omega')$.
A shortest path, thus, would be a path $\omega \in \mathcal P_{s,t}$ that minimizes $\ell$ when restricted to $\mathcal P_{s,t}$.
If we have a cycle $c$ connected to both $s$ and $t$ via paths $\omega_s,\omega_t$, then $\omega_s c^k \omega_t$ is also a path from $s$ to $t$ that goes trough $\omega_s$ then loops around $c$ for $k$ times, and then goes through $\omega_t$. By direct computation,
$$
\ell(\omega_s c^k \omega_t) = \ell(\omega_s) +k\ell(c)+\ell(\omega_s). 
$$
Hence if the cycle $c$ is negative, by the previous formula the function $\ell$ takes arbitrarily large negative values in $\mathcal P_{s,t}$ and thus can't attain a minimum value.
Now, your task is to show the converse. Also, note that to be a problem we needed the aforementioned cycle to be connected to $s$ and $t$. If we have negative cycles in, say, a disjoint connected component from the one of $s$ and $t$, it has no impact on the cost of paths $s \to t$.
Edit: okay, some more thoughts for the converse. What I've come up with may be a bit cumbersome, I hope someone posts a clever proof soon. But anyway, here's my attempt:
Fix $\omega$ a path for $s$ to $t$. If $\omega = \omega' c \omega ''$ with $c$ a positive (or rather non-negative) cycle, then $\ell(\omega) \geq \ell(\omega' \omega'')$. Thus, to check wether $\ell$ attains a minimum value, we can restrict ourselves to paths without non-negative cycles.
But then, by hypothesis, the paths considered have no cycles. If your graph is finite, there are a finite amount of vertices and so without making a cycle there are finite options for a path from $s$ to $t$, i.e. the subset $S \subset \mathcal P_{s,t}$ of acyclic paths is finite. Hence $\ell$ attains a minimum in $S$, and by the previous observation this is a minimum in $\mathcal P_{s,t}$.
