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 to
by kevinwang 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?
> Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology.
- foota 2y agoNo, I don't believe so. It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex", but A* only explores a subset of vertices based on the heuristic, so it can be more efficient.
- 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.