algorithm - K negative edges - single source shortest path -

i've managed solve problem finding single source shortest paths when there's 1 negative edge using dijkstra.

now i'm trying face new problem, how find shortest paths given source when there k negative edges using dijkstra (not bellman ford). (k known).

can't think of way it.

any suggestions?

if nondirectional graph, there no single shortest path because single negative edge, go , forth on negative edge , have infinite number of paths of negative infinity.

however, assuming directional graph no negative cycles, use breadth first search , keep track of both negative edges you've hit , shortest path each node you've discovered far. if see node you've visited, go there again if better previous path took there.

since there no negative cycles algorithm must terminate. after algorithm terminates target node should have best path used there.