> There are objectively correct ways to search a graph
Objectively false.
Years ago I was talking to some sort of CS professor who had been specializing in networking. He mentioned that within an organization you typically see network's being mapped out with dijkstra, but between them (with BGP for example) you actually see packets routed the long way around. He claimed service providers did this because it allowed them to charge their competitors more money when they had to use their network. Although, a more charitable interpretation is perhaps that a service provider will naturally want its own traffic to have the best experience and will send their competitors traffic the long way so that they don't over saturate the network of their primary customers.
Perhaps the best of all worlds would be mapping your network such that your primary customers get the optimal path using dijkstra. Then you figure out how to get your competitor's traffic routed as fast as possible without dropping your primary customer's packets. Maybe something a genetic algorithm might be good at figuring out?
There are some objective things in this world. The optimal way travel from point a to point b in a graph is one of them. However, this is the optimal way to travel, not the objectively correct way to travel.
I once traveled home from work using the backroads in a move that cost me probably 30 extra minutes. Roads are a graph. I followed the objectively non-optimal path. However, the way the clouds were that day formed something like 20 rainbows. Which I got to gawk at the whole way home. Objectively non-optimal, but not objectively incorrect.