[its_bbq]

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]

Eh? 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).

[its_bbq]

Yes I meant specifically for Kevin Bacon. There are other all pairs shortest paths algorithms besides running Dijkstra N times

[compsciphd]

oh 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.

[ant6n]

But there's only one Kevin Bacon.

I mean there's also Erdos, but that's a different story.

[its_bbq]

Erdos-Bacon number is a join and sum ;)