I had checked on some websites and they said that when Dijkstra went through a node, it marked that node as optimized and never visit again. But now, I implement Dijkstra with priority queue and compare by checking if distance[v] > distance[u] + w. By that way, it will just get the most optimized way for a node without getting trouble with negative weights.
Here's an example of my Dijkstra code to attempt High Score problem on CSES. My code uses Dijkstra to find the optimal path to the final path and also using the SPFA's trick (count if node is visited more than n times).
My code got Accepted on most of the testcases (except the only one testcase that got Wrong Answer because it detects the wrong cycle — and I don't know why)
Can someone help me explain this? I know that I'm wrong somewhere but I'm so confused. Thank you!
In case of a negative cycle, it will run but give wrong answer since we can keep revolving around negative cycle to minimize distance and then get to destination ideal answer is -INF in this case, incase of negative weights but not negative cycle it will miss on the optimal path, since there could be a case that A -> C takes 2 units and A -> B takes 4 units but B ->C takes -3 units so it will miss the 1 unit shortest dist for C.
In case of the negative cycle, I tried SPFA trick so I think that would be possible to detect the cycle and exit early.
With your example of the negative weight. My code will process:
Process A:
dis[A] = 0,dis[B] = 4,dis[C] = 2(now B and C are in priority queue)Process the one with least weight (C): none (now priority queue left with B)
Process next one with least weight (B):
dis[C] (2) > dis[B] (4) - 3so it update the distance:dis[C] = 1.So it still can find the optimal way.
Ya so the SPFA actually solves the issue of Negative weight but not negative cycle,if the cycle itself is negative then it will keep moving in circle since everytime it visits any cyclic node it will have a decreased distance eg: — A -> B = 3 , B->C = -3 and C->A = -4, now A is 0 at start but when it reaches A again the dist is -4 so it updates now again when it reaches A it becomes -8 so on and so forth, so it becomes an infinite loop. Dijkstra wouldnt run into infinite loop since we dont visit a node twice but it fails for negative edges since it misses optimal Path, SPFA corrects it by visiting a node again but then it goes into a infinite cycle due to negative cycle.
Ok, so can we use SPFA trick on Dijkstra to know that it is a negative cycle and how about the graph with no negative cycles but negative weights?
Its actually the opposite, u can use SPFA for non negative cycles, since it finds the the optimal path after going through all paths (unlike dijkstra who goes only once per node). Incase of negative cycle u can search up bellman ford algorithm, it relaxes nodes n-1 times to get optimal way we do it once more to check if there is a negative cycle. U can use SPFA for negative cycles as well but u need to do additional modifications (that i never did so no idea here) to detect if it is falling into a infinite loop.
Actually, your code is not Dijkstra, but rather a classic false optimization of SPFA, which has an exponential complexity assuming no constraint on edge weight, but it seems that the problem test data did not try to hack this solution.
The reason why it gives WA is probably simply just because you set the distance of $$$n$$$ to $$$-1$$$ without checking if node $$$n$$$ is actually reachable by the nodes on the negative weight cycle.
You are right, it is not Dijkstra. But I've checked if the nodes on the negative weight cycle is reachable by n and even if 1 is reachable to them with the
visandvis2bitset.the problem is from
cnt[v.u].when i removed it, i got AC on that testcase but RTE and TLE on the rest of the tests.
Also why are you using dijkstra to find the longest path.
Dijkstra's algorithm cannot be used in graphs with negative weights.
That's what I'm asking. Why it can't be used in negative weights graph? As I described on the top comment. I can't find an example that it can't be used. I added that cnt array just to copy the SPFA trick on counting the node visiting times.
And I do High Score with Dijkstra with the testing purpose to see if Dijkstra is good on negative weights and find out why
dijkstra geedily gives a distance (dist[node]) once a node is visited . That distance never changes and assumed as the minimum path to the source.
negative weights break that assumption .
You can also think of it like this. the longest path problem is NP-Hard, dijkstra is P. so dijkstra can't solve longest path problem.
This is wrong. The longest simple path is NP-Hard. In this problem we are allowed to visit the same vertex or use the same edge multiple times, and it is very much solvable in polynomial time.
if you can solve that problem with dijkstra then
and you get 1 Million dollars
it will run INF times that's why it's no suitable for negative weights
Dijkstra works on the assumption that the minimum distance in the priority queue will always increase (or stay the same) with time. But having negative edges breaks this assumption.
but it can always update that node back if I use priority_queue instead of making a visit array. So it can be updated many times when the path is more optimized (unless it has a negative cycle). After some research I see that Dijkstra gonna do some backtrack $$$2^n$$$ approach on some "Killer" tests. But I can't find any simple test that counter my Dijkstra
Actually, you can solve it using Dijkstra like structure, but only if you understand the logic behind the Bellman Ford
code: MY AC CODE O(n²) also you can use priority queue but time will be O(n² log n²)
Consider a directed graph like this (
v u cost,Cis some big number):In words: vertices come in groups of 3, it is very expensive to go from the first vertex in the group to the second, but then from the second to the third is negative s.t. going from the first to the third is actually $$$-2^k$$$, but you need to go through the second vertex. And from both the first and the third there is an edge of weight $$$1$$$ to the start of the next group.
The graph is clearly acyclic, since we only have edges from vertices with smaller ids to vertices with bigger ids; so there are no negative cycles (because there are no cycles). When you run your dijkstra from vertex $$$1$$$, you will update the distance to vertex $$$4$$$ and to vertex $$$2$$$. Then you will proceed from vertex $$$4$$$ with the rest of the graph, and all distances generated will be smaller than $$$C$$$, so you'll have to run the full traversal from vertex $$$4$$$ before processing vertex $$$2$$$. But then you will reach vertex $$$3$$$, which will in turn update vertex $$$4$$$ with a much smaller distance, so you'll have to run the whole thing from $$$4$$$ again.
Thus each new group makes you run dijkstra on the rest of the graph twice, which means that number of vertices visited will be of order $$$O(2^{n/3})$$$. $$$n$$$ is just $$$90$$$ because I need exponentially big weights to construct the example (and actually each time you process a vertex it means that the distance to it was decreased, and if the distances are integers that would mean that each vertex is processed at most $$$O(nW)$$$ times (where $$$W$$$ is bound on absolute value of edge weight) before you can establish that there is a negative cycle), but it is exponential in $$$n$$$.
If I want to be pedantic (and I do): this is not Dijkstra. The whole concept of Dijkstra is that once we decide to process a vertex, we are sure it has the correct distance now, and we will never have to process it again. It's a greedy algorithm, and it can be proven for non-negative weights. It is incorrect for negative weights (use the same example as above, except once we go through the rest of the graph from vertex $$$4$$$ we can't change it, so we wouldn't be able to go through vertex $$$3$$$ further).
Thank you so much! This is what I'm asking for. Also thanks everybody for helping me!! I think Dijkstra gonna help me pass some testcases in the future lol (if I'm lucky)