I need help in finding cycle with minimum weights in an undirected graph.Basically i am looking for an efficient approach , of lower time complexity than that of applying dijkstra after removing every edge and adding that back, it has time complexity of O(E^2logV). So something better than this..
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.11.2024 17:54:08 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
If you use Floyd-Warshall to find the minimum cycle,the complexity is O(v^3).Maybe it can run faster in a graph that the number of edges is a lot larger than the number of vertices.And this one,as well as the one you mentioned above,is the most efficient way to find the minimum cycle in a graph.
Why so many downvotes?
From what I understand, the same edge can't be used twice as otherwise the problem would be as simple as double the smallest edge. Floyd-Warshall would use the same edge twice so it wouldn't be correct.
I think he meant not just simply do Floyd-Warshall. And indeed it can find the minimum cycle without using the same edge twice.
The main idea is before we try to update dist(u, v) with vertex w, we know that dist(u, v) doesn't contain vertex w, so we can update ans to min(ans, dist(u, v) + edge(u, w) + edge(w, v)).
Maybe you misunderstand what I mean,it's obviously wrong that we use the minimal distance from i to i to update the answer.Instead,when we do FLoyd,before we update dis[i][j] by dis[i][k]+dis[k][j]，we can update our answer by dis[i][k]+dis[k][j]+dis[j][i].And it's proved to be correct.
Yes，what I meant is just the same as what Bedge said.
Thanks.. :)