4 ms·
You're technically correct, but afaik there isn't really a way to compute transitive closure without also computing shortest paths along the way, modulo constan
by whoisburbansky 6y ago
You're technically correct, but afaik there isn't really a way to compute transitive closure without also computing shortest paths along the way, modulo constant factors?
- simcop2387 6y agoYou'll compute paths along the way but won't know that they're the shortest path. Odds are good though that you'll havr found something good enough for most purposes though.
- whoisburbansky 6y agoIf all you do is iterate over the adjacency matrix, sure, but wouldn't Floyd-Warshall be the same time complexity? All I'm saying is that you get both pieces of information for essentially the same price, modulo constant factors.