Teacher say: Given a directed a-cyclic graph $G = (V , E)$, with negative edges weights, now We can claim that, Dijkstra's relaxation function do $\Omega(2^n)$ relaxation edges, but every times i think, i get stuck to prove it. In addition, I found reference of This problem come from "Jeff Erickson, Algorithms text book".
Anyone can give me a hint to construct an example to prove it?
The standard implementation of Dijkstra does not work with negative edge weights. This is due to its greedy nature. Here is an example:
Consider the directed graph $G=(V,E)$ with $E=\{(a,b, 4), (a, c, 2), (b, c, -3)\}$ and assume that we want to find the shortest path from $a$ to $c$. Dijkstra's algorithm will extract vertex $c$ from the queue before it will extract $b$ and report $2$ as the shortest path from $a$ to $c$. But the correct answer would have been $1$ ($a \to b$, $b \to c$).
However, if we restrict $G$ to the acyclic case, we can make Dijsktra’s algorithm work for negative weights but we must allow visiting vertices more than once (meaning, we do not mark vertex $c$ as closed).
However, this leads to calculating each possible path from $a$ to $c$ and in the worst case there are $2^{n-2}$ possible paths in a directed acyclic graph on $n$ vertices (checkout this question and its answers), thus $\Omega(2^n)$.