If you tap the F1 key and type in AllPairsShortestPath and hit Enter and click on Details do you then see
To use AllPairsShortestPath, you first need to load the Combinatorica Package using Needs["Combinatorica`"].
If you get a warning message after you evaluate that Needs then just ignore it, they duplicated some, but not all, of the Combinatorica package in the math kernel and it is just letting you know that.
Unfortunately somehow the dancing blinking red hand with the finger pointing at "Details" with a little thought bubble above it saying "Click me, Click me" was left out of the build. So many questions have the answer hiding behind that and it gets missed far too often.
