Sort the vertices topologically, then relax each edge exactly once: shortest (or longest) paths in O(V + E), negative weights and all.
This interactive visualization needs JavaScript.