Do it! Like it! Frenf it!

Evaluate World Peace

profile_pic

larsen to dewdney-ita, larsen

"Negative-Weight Single-Source Shortest Paths in Near-linear Time". Siamo freschi di AOC quindi ricorderemo l'algoritmo di Dijkstra. Una delle condizioni per applicarlo è che i pesi degli archi del grafo siano positivi. Ebbene, gli autori dell'articolo hanno trovato un algoritmo per risolvere il più generale "Negative-Weight SSSP Problem" in una maniera che a quanto pare è semplice ed efficiente https://arxiv.org/abs/220...