Lo que tú consideras un fallo, no es tal. El algoritmo de pantalaimon es óptimo, siempre encuentra el mejor camino. Eso no quiere decir que el mejor camino sea perfecto para todos los casos.
En cuanto al reto de mcd y MCD, aquí está mi código:
http://jsfiddle.net/marlanga/Gsw9B/1/
Se basa en la misma idea que el resto de envíos, aunque para darle un poco de chicha lo he hecho parecido al de pantalaimon; en vez de un array de números, lo que acepta es un número infinito de argumentos numéricos sobre los que calcular las operaciones. Por supuesto, con un apply, es posible también meterle un array.