| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427613 | Information Processing Letters | 2013 | 4 Pages |
Abstract
The purpose of this note is to give a short proof that a standard model for the Physarum polycephalum slime mold correctly computes the shortest path in an undirected weighted graph [V. Bonifaci, K. Mehlhorn, G. Varma, Physarum can compute shortest paths, in: Proc. of the 23rd ACM–SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 233–240].
► Physarum is a slime mold giving rise to a “natural algorithm” for the shortest path problem. ► A standard model for Physarum converges to the shortest path in any network. ► Very mild assumptions on the input data allow for a much shorter proof of convergence.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vincenzo Bonifaci,