undefined | Better HN

0 pointsmlyle1y ago0 comments

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

0 comments

foota1y ago

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

j / k navigate · click thread line to collapse

0 pointsmlyle1y ago0 comments

> > 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?

0 comments

foota1y ago

j / k navigate · click thread line to collapse