The naive dynamic programming solution doesn't work because it's possible to 'backtrack'. But I used Bellman-Ford which is almost as simple and very fast.