動的計画法（最短経路）

/****************************/
/* 動的計画法（最短経路）   */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

class Search
{
	/********************************************/
	/* 動的計画法（最短経路）                   */
	/*      n : ノードの数                      */
	/*          　ノード0:スタート              */
	/*          　ノード(n-1):ゴール            */
	/*      r : ノード間の距離                  */
	/********************************************/
	static void dynamic(int n, int r[][])
	{
		int i1, i2, r1, nx = 0, k1 = 0, k2 = 1, rd[][] = new int [2][n];
		boolean sw = true;
					// 初期設定
		for (i1 = 0; i1 < n; i1++)
			rd[0][i1] = -1;
		rd[0][0] = 0;
					// 実行
		while (sw) {
			if (nx%2 == 0) {
				k1 = 0;
				k2 = 1;
			}
			else {
				k1 = 1;
				k2 = 0;
			}
			sw = false;
			for (i1 = 0; i1 < n; i1++) {
				rd[k2][i1] = rd[k1][i1];
				for (i2 = 0; i2 < n; i2++) {
					if (rd[k1][i2] >= 0 && r[i2][i1] >= 0) {
						r1 = rd[k1][i2] + r[i2][i1];
						if (rd[k2][i1] < 0 || r1 < rd[k2][i1]) {
							rd[k2][i1] = r1;
							sw         = true;
						}
					}
				}
			}
			nx++;
		}

		System.out.printf("ステップ： %d，　最短距離： %d\n", nx, rd[k1][n-1]);
	}
}

public class Test
{
	public static void main (String[] args)
	{
		int i1, i2, r[][] = new int [7][7];

		for (i1 = 0; i1 < 7; i1++) {
			for (i2 = 0; i2 < 7; i2++)
				r[i1][i2] = -1;
		}
		r[0][1] = 2;
		r[1][0] = 2;
		r[0][2] = 5;
		r[2][0] = 5;
		r[1][2] = 4;
		r[2][1] = 4;
		r[1][3] = 6;
		r[3][1] = 6;
		r[1][4] = 10;
		r[4][1] = 10;
		r[2][3] = 2;
		r[3][2] = 2;
		r[3][5] = 1;
		r[5][3] = 1;
		r[4][5] = 3;
		r[5][4] = 3;
		r[4][6] = 5;
		r[6][4] = 5;
		r[5][6] = 9;
		r[6][5] = 9;

		Search.dynamic(7, r);

	}
}