Glanced at the exercises. It appears that two of them have numbers arranged in a triangle and ask for a longest path.
Hmm. Given such a triangle, let m be the largest number in the triangle. For each x in the triangle, replace it with m - x. For the resulting triangle, solve it to give the shortest path using one of the well known network shortest path algorithms.
> Hmm. Given such a triangle, let m be the largest number in the triangle. For each x in the triangle, replace it with m - x.
By the time you've actually done these two steps, you could have already finished the problem with a dynamic programming approach.
(Starting from the bottom row and working upward, replace each cell in the row with the length of the longest path from itself to the bottom, which you can know by checking which of its two children has the longer path associated.)
The "well known" path algorithms in this case are overkill; the graph is a tree. And Dijkstra is not really designed to handle negative edge weights (although it would probably function correctly in this instance).
Hmm. Given such a triangle, let m be the largest number in the triangle. For each x in the triangle, replace it with m - x. For the resulting triangle, solve it to give the shortest path using one of the well known network shortest path algorithms.