  Distributed consensus has been intensively studied in recent years as a means
to mitigate state differences among dynamic nodes on a graph. It has been
successfully employed in various applications, e.g., formation control of
multi-robots, load balancing, clock synchronization. However, almost all
existing applications cast an impression of consensus as a simple process to
iteratively reach agreement, without any clue on possibility to generate
advanced complexity, say shortest path planning, which has been proved to be
NP-hard. Counter-intuitively, we show for the first time that the complexity of
shortest path planning can emerge from a perturbed version of min-consensus
protocol, which as a case study may shed lights to researchers in the field of
distributed control to re-think the nature of complexity and the distance
between control and intelligence. Besides, we rigorously prove the convergence
of graph dynamics and its equivalence to shortest path solutions. An
illustrative simulation on a small scale graph is provided to show the
convergence of the biased min-consensus dynamics to shortest path solution over
the graph. To demonstrate the scalability to large scale problems, a graph with
43826 nodes, which corresponds to a map of a maze in 2D, is considered in the
simulation study. Apart from possible applications in robot path planning, the
result is further extended to robot complete coverage, showing its potential in
real practice such as cleaning robots.
