4 ms·

Someone has described using a physical network to solve the shortest-path problem in O(N) time: https://www.reddit.com/r/compsci/comments/a1sqb/help_shortest_di

• cauterized 10y ago
  That doesn't seem right to me. You'd have to tie a string between every single possible pair of nodes, so it's O(N^2).
  • jameshart 10y ago
    The wiffle-ball-graph data structure is O(n) for insertion, sure (each new ball has to be tied to a bunch of existing balls and finding them is probably O(n) at best), so building an n-node wiffle-graph is O(n^2), but shortest path queries on the data structure are O(n) at any time (again because you have to go find the two nodes of interest, then spread them apart by at most n units of distance). You can also sort all the nodes by distance from any given node in O(n) time by holding the chosen wiffle ball and hanging the graph over the edge of an O(n) tall tower.
    • deleted 10y ago
      [deleted]