Physarum can compute shortest paths.

Vincenzo Bonifaci, Kurt Mehlhorn, Girish Varma

Browse the full SODA paper archive.