# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Physarum Can Compute Shortest Paths

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bonifaci, V., Mehlhorn, K., & Varma, G. (2012). Physarum Can Compute Shortest Paths.
In Y. Ravani (*Proceedings of the Twenty-Third Annual ACM-SIAM
Symposium on Discrete Algorithms* (pp. 233-240). Philadelphia, PA: SIAM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-BB81-8

##### Abstract

Physarum Polycephalum is a slime mold that is apparently able to solve shortest
path problems.
A mathematical model has been proposed by biologists to describe the feedback
mechanism used by the slime mold to adapt its tubular channels while foraging
two food sources s_0 and s_1. We prove that, under this model, the mass of
the mold will eventually converge to the shortest s_0-s_1 path of the
network that the mold lies on, independently of the structure of the network or
of the initial mass distribution.
This matches the experimental observations by the biologists and can be seen as
an example of a "natural algorithm", that is, an algorithm developed by
evolution over millions of years.