" Dijkstra works when distance/cost is monotonic i.e all positive edges or all negative edges. But there shouldn't be any negative cycles "
can some make me understand the negative edges part , Thanks :D
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 03:39:32 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
negative cycles mean that there is some cycles whose cost (sum of composing edges) is negative. There shouldnt be such negative edges because then the algorithm does not make sense (the cost to get from A to B is negatively infinite as you can go through that cycle for as long as you want, making the cost infinitely small, and if you want, at some point you can leave the cycle and go towards B (but you could've still made the cost smaller by continuing on the cycle))
One correction here, there can be negative edges in the graph for dijkstra to work, but in case of negative cycle, it will go into an infinite loop.
No i think this is wrong. If negative edges exist in the graph, the dijkstra's algorithm doesn't work. This is because dijkstra's algorithm is based on a greedy assumption that does not hold true when negative edges exist.
Also, dijkstra never goes into an infinite loop in any circumstance, even when there are negative cycles. Dijkstra always runs in O((n+m)logn) time. This is because dijkstra will never visit vertices which have already been visited.
I think you need to get your facts right. You can refer to this article from GFG. Dijkstra may work in some cases where there is a negative edge but not in all of them.
Eg : Consider a loop like this in a graph with three nodes A, B and C : A->B->C->A.
Assume :
A -> B has weight -1.
B -> C has weight 5.
C -> A has weight 4.
Here Dijkstra will work perfectly fine as the cycle has a positive cumulative weight.
For the second part (about the infinite loop) you can refer this.
Hope this helps.
An algorithm is only considered correct if it works in every testcase. Therefore, i am still correct in saying that dijkstras algorithm doesnt work when u have a negative edge.
as for the negative cycle, it depends on your implementation of dijkstras. When i implement it, i make sure that i never visit the same vertex twice so i will never enter an infinite loop.
However, the conclusion still remains that when negative edges exist, dijkstras algorithm is incorrect.
Also, just to clarify, are you saying that if a graph has negative edges but only positive cycles then dijkstras algorithm will work? If so then that is incorrect as well. And if u want an example, it exists in the second link that u posted urself
I think you haven't read my reply correctly. I clearly mentioned Dijkstra may work in some cases where there is a negative edge but not in all of them. Try reading the reply again.
I know what u said man. But what ur not understanding is that if it doesnt work in some cases then it doesnt work at all. I know that it may be hard for u to wrap ur head around that but thats how algorithms work. Unless it works in every testcase and every scenario, it may as well be useless.
Got your point bro. I just tried to explain the statement in the blog
When ur doing a contest, do u try to make an algorithm which always works or sometimes works? U will obviously try to make an algorithm which always works becos if it doesnt always work then ur code will produce a wrong answer in one of the testcases and u wont get any points. So if its not correct in every testcase, then it isnt correct at all. Thats all im saying
(https://cses.fi/problemset/task/1680) [In this problem, I converted all edge weights to -1 and performed a Dijkstra it gave correct ans , upon searching about it I came across this statement , that Dijkstra require monotonic edge weights (either all positive edges or all negative edges, also no cycle.] [Solution](https://pastebin.com/yn6A9RJ2)
Here Dijkstra worked because there were no directed cycles i.e. no negative cycles as I mentioned above.
So using -1 as edge weight will return maximum distance instead of minimum.
It's interesting because even though you are right that dijkstra will correctly calculate maximum distance instead of minimum, if im not wrong, then time complexity of dijkstra will no longer be O((n+m)logn). Instead, in specific testcases, i think it will go up to O(n*(n+m)logn). basically multiplying by an additional factor of n. Pls respond if you want explanation of why i think this is the case.
I think we should use simple BFS instead of Dijkstra because all edge weights are the same.
That will run in much lesser time complexity.
And I think you are right.