4 ms·
> > When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. > But that statement doesn't apply
by mlyle 2y ago
> > When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's.
> But that statement doesn't apply to the version of Dijkstra's developed in this paper right?
Simple thought experiment: I have an algorithm that has path costs for one graph memorized and first compares to that graph; it's O(V+E) to compare and return the value for that memorized graph. It obviously beats this algorithm for that graph.
- foota 2y agoHm... technically they're saying that their algorithm performs as well as possible "for every single graph topology". Your special cased algorithm would only work for one particular graph in a family of isomorphic graphs (unless you have a linear time algorithm for the graph isomorphism problem, in which case please share), but would fail for the rest of the graphs in the family. So I think you could still say that their algorithm performs as well as possible for that topology.