4 ms·
This is the low-hanging fruit algorithm: - build the DAG with heavy nodes (e.g. lead split-shot) - use string or fishing line for edges, with length proportio
by mikhailfranco 3y ago
This is the low-hanging fruit algorithm:
- build the DAG with heavy nodes (e.g. lead split-shot)
- use string or fishing line for edges, with length proportional to 'weights'
- hold the root node(s) high in the air, if more than one, hold them together, at the same height
- the lowest node, or the length of taught line (drop distance below your hand), is the answer
- roughly 3y agoWhat’s great is that it’s constant time, once you’ve prepared the data structure. Never underestimate the parallelism of physical systems.
- a1369209993 3y agoThat doesn't actually work, because a DAG only lacks directed cycles. Consider: /-3-> D A -1-> B -1-> C \------4------^ In this case, the longest path is A-C, but C will be held at level 2 by B, leaving D lowest at level 3. This works for a fully-acyclic directed graph (eg a tree), but not for a directed-acyclic directed graph. It can also find the node whose shortest path is the longest (so longest shortest path, minimax style). (It also works for a acyclic undirected graph, as illustrated at [0], but that's a bit tangential.) 0: https://www.youtube.com/watch?v=wGrOPSBPpyk https://www.youtube.com/watch?v=wGrOPSBPpyk
- mikhailfranco 3y agoYes, you are completely correct. It only works for fruit trees.
- a1369209993 3y agoActually it works for all trees, fruit or otherwise (and also for some non-tree graphs, though I'd have trouble giving a useful category more general than tree).