5 ms·
They call the dijkstra implementation slow but that's because they aren't using the full information it presents. Dijkstra gives shortest paths from one node to
by its_bbq 2y ago
They call the dijkstra implementation slow but that's because they aren't using the full information it presents. Dijkstra gives shortest paths from one node to every other node in the graph, so you run it once and materialize it and now you have a full Kevin Bacon database
- compsciphd 2y agoEh? you have a full graph of one node to every other node. not shortest path between every pair (which I assume is what a full kevin bacon database would be).
- ant6n 2y agoBut there's only one Kevin Bacon. I mean there's also Erdos, but that's a different story.
- its_bbq 2y agoErdos-Bacon number is a join and sum ;)
- its_bbq 2y agoYes I meant specifically for Kevin Bacon. There are other all pairs shortest paths algorithms besides running Dijkstra N times
- compsciphd 2y agooh that's true, for some reason I was thinking path from A->Bacon. But dijkstra from Bacon->A is just as computational intensive and much more valuable to keep around.