Hi all,
Apparantly there is way to find SSSP from a single point, but I have tried a while and could not come with it. Can anyone help?
There is article here, but I have to buy it for USD$31.50.
So anyone can tell me about the algorithm for free?
Thanks,
-minimario
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 151 |
| 3 | maspy | 150 |
| 4 | AmShZ | 143 |
| 4 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | Proof_by_QED | 131 |
We need data structure to find "one" adjacent vertex, and remove that vertex. Use max segtree.
Oh, thank you very much, I see now. I overlooked something so simple :)
Algorithm itself is easy, but I'm not sure coming up with this is also easy :p
Sorry, ignore it! But I can't delete it :)
It's okay :)
Not sure about that linear one, but I think it's quite easy to handle weighted version with this algorithm.
Note that relaxation is necessary for only one time. It's due to the fact the weight is in vertex, not edge.
Btw you can use sci-hub.io to get the paper for free.
BTW, are there any interesting problems that use some properties of this graph?