4 ms·
The optimization can't generalize to weighted graphs, because the first visit is not guaranteed to be the final shortest path: a path with two edges can have le
by mikhailfranco 6y ago
The optimization can't generalize to weighted graphs, because the first visit is not guaranteed to be the final shortest path: a path with two edges can have less weight than the first visit along one edge.
But hey, it's been reviewed by Tarjan. I must be wrong.