Disclaimer: If it was not clear to you already, this article is not about an algorithm which is practical on computare hardware. It is about a "natural" algorithm, working based on physical/real-life principles. It may give you some insights on algorithmic thinking, though. Either way, it's interesting to know this.

In this article, I will discuss about an interesting data structure that can deal with all of the following operations in $$$O(1)$$$ time and $$$O(V+EW)$$$ space complexity. The operations are:

• $$$link(u,v,w)$$$: Connect two vertices $$$u$$$ and $$$v$$$ with an edge of weight $$$w$$$.
• $$$cut(e)$$$: Cut the edge $$$e$$$.
• $$$mpath(u,v)$$$: Find a shortest path between two vertices $$$u$$$ and $$$v$$$, if one exists.
• $$$connected(u,v)$$$: Check if two vertices $$$u$$$ and $$$v$$$ are connected.

Here are how each operation works and are implemented.

"Base structure"

Each vertex is an object where you can tie a string on. A plastic ring should work fine. Each edge is a flexible (but not elastic!) string with a certain length. A (practically infinitely) long thread of string, and a pair of scissors is maintained for future use. This is the "base structure" of this data structure.

$$$link(u,v,w)$$$

Grab your pair of scissors, and cut out a string of length $$$w$$$, and connect vertex $$$u$$$ and $$$v$$$ with the string physically. This is practically $$$O(1)$$$ in time complexity, and contributes $$$O(W)$$$ to the space complexity.

$$$cut(e)$$$

Grab your pair of scissors, and cut the string corresponding to the edge $$$e$$$. This is $$$O(1)$$$ in time complexity, and garbage collection can work nicely as well. (Just throw away the string into the bin.)

$$$connected(u,v)$$$, $$$mpath(u,v)$$$

These two operations are basically one operation in reality. This operation can be interpreted as the following linear program.

Now, if you're accustomed to linear programming, you might realize that this is the LP formulation of shortest paths on an undirected graph. Now, what we did for each $$$link$$$ and $$$cut$$$ operation just translates to the constraints in this linear program. Because we connected $$$u_e$$$ and $$$v_e$$$ physically with a string of length $$$w_e$$$, the two vertices cannot have a distance farther than $$$w_e$$$. The only step left is to bind $$$X_u=0$$$ and maximize $$$X_v$$$.

Maximizing $$$X_v$$$ is not hard. You can just grab $$$u$$$ and pull $$$v$$$ forcefully towards some direction until you cannot pull further. Now that the linear program is complete physically, we have just found the result in $$$O(1)$$$ time. If you can pull infinitely, the linear program is unbounded, which means the two vertices are disconnected. If you cannot pull further than some distance, that distance is the shortest path, and the path connecting $$$u$$$ and $$$v$$$ in a straight line now is the shortest path.

Conclusion

With physical principles, we just found out that time complexities that seem impossible can in fact be possible in natural algorithms. How fascinating it is to know what physics can provide us in algorithms! I hope this article could give you some insights on algorithmic thinking, or at least keep you interested throughout the article.