Dynamic Programming

This is an implementation of a dynamic programming algorithm finding the cheapest voyage from node 0 to node 1. The costs of a direct voyage from node x to y are stored in "price[x,y]" and the initialization of these values is a bit random and a bit chosen such that the outcome is interesting. The variable "next[x]" contains the place to which to go from "x" in order to reach the node 1 as cheap as possible. The variable "costs[x]" tells how expensive the voyage from "x" to 1 is at least. The implemented function computing the variables "next" and "costs" is the following:

function dynamicprogramming()
  { var i; var j; var k;
    next[n-1]=n-1; costs[n-1]=0;
    for (i=n-2;i>=0;i=i-1)
      { k = n-1;
        for (j=n-2;j>i;j=j-1)
          { if (price[i][j]+costs[j]<price[i][k]+costs[k]) { k = j; } }
        next[i] = k; costs[i] = price[i][k]+costs[k]; } }

The parameter "n" holds the number of points. The final destination has the value n-1, the starting point the value 0. One can only go from smaller nodes to larger ones.

Java Script starts here.

Java Script ends here.