Re:SQLite now allows multiple recursive SELECT statements in...
by whoisburbansky on Wednesday October 21, 2020 @12:35AM
(#24844764)
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?
[ Parent
| on HN ]
Re:SQLite now allows multiple recursive SELECT statements in...
by simcop2387 on Wednesday October 21, 2020 @12:54AM
(#24844838)
You'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.
Re:SQLite now allows multiple recursive SELECT statements in...
by whoisburbansky on Wednesday October 21, 2020 @01:00AM
(#24844871)
If 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.