It does work just the way you think!
Look at the proof at wikipedia. The fact that all the edges are assumed positive is used when they say that dist[w]>dist[v]
is a contradiction because as there can not be a negative weighted path from w
to v
, v
must come first.
Here it continues to be a contradiction because otherwise, there would be a negative weighted path from w
to v
, which means it uses a negative edge, that is an edge from source
, which is absurd because that would mean dist[w]>dist[w,source]
, i.e. a negative cycle.
BONUS
I'll proof that the approach proposed in @dtldarek
's comment is also correct.
It is trivial that the shortest path from source
to target
uses no return edges to source
, thus the shortest path can be selected from the set $P$ of those paths which don't return to source
ever.
It is also clear that every path in $P$ uses exactly once one of the outgoing edges from source
. (We may assume source
is not the same node as target
).
Therefore by adding a constant $K$ to every outgoing edge from source
so that they are all positive, all the paths in $P$ will increase their lengths by $K$. If we call $P'$ this set of modified paths, we can claim
$min\{length(p) : p \in P\} \\
=min\{length(p)+K-K : p \in P\} \\
=min\{length(p)+K : p \in P\}-K \\
=min\{length(p') : p' \in P'\}-K$
and conclude that it suffices running dijkstra on the modified graph and substrating K.
I'm not sure I completely get the question -- you are having trouble understanding Dijkstra's algorithm? The Wikipedia article is good, and there are many nice worked examples on the web. I would try to work through some of these examples, and then ask specific questions if you're still confused about how the algorithm works.
As for the homework problem you've quoted, here's a hint: any algorithm, Dijkstra or otherwise, for finding a shortest path will only work if such a path actually exists. Can you come up with an example of a connected weighted graph where no shortest path exists between some pair of nodes?
Best Answer
Assign every edge weight $-1$. Then the shortest cycle in your digraph is the longest cycle in the unweighted digraph. Therefore computing the answer would yield the result to the np-complete directed hamilton-cycle problem. If $\text{P}\neq\text{NP}$ you can therefore find no polynomial algorithm to compute the shortest cycle. You will therefore not come around finding all cycles in the graph, a discussion on how to do this can be found here.
The algorithm you describe is polynomial as far as i can tell (you essential run $n$ times dfs which is linear in time).