dijkstra's algorithm with negative edges on a directed graph

Question

What if the only negative edge costs are coming from the initial node? Will the algorithm still work?

I feel like yes because I can't think of a counter-example, but I'm having trouble proving it. Anyone have a counter-example?

Negative edges are a problem for Dijkstra's because there's no guarantee that the edge you pick produces the shortest path if there is an edge you can pick later that is largely negatively weighted. But if the only negative edges are coming out of the initial node, I don't see the problem.

I'm not looking for an algorithm. I'm looking for some insight into the Dijkstra's.

[EDIT] Sorry! I forgot to add that I'm talking about a directed graph, if that makes a difference.

Answer 1

Counter-example:

Graph G = (V, E), with vertices V = {A, B}, edges E = {(A, B), (B, A)} and weight function w(A, B) = -2, w(B, A) = +1.

There's a negative weight cycle, hence minimum distances are undefined (even using A as initial node).