動的計画法（最短経路）

/*********************************/
/* 動的計画法（最短経路）        */
/*           coded by Y.Suganuma */
/*********************************/
#include <stdio.h>

/*********************************/
/* 動的計画法（最短経路）        */
/*      n : ノードの数           */
/*          　ノード0:スタート   */
/*          　ノード(n-1):ゴール */
/*      r : ノード間の距離       */
/*********************************/
void dynamic(int n, int **r)
{
	int i1, i2, r1, nx = 0, k1, k2, **rd;
	bool sw = true;
					// 初期設定
	rd = new int * [2];
	for (i1 = 0; i1 < 2; i1++)
		rd[i1] = new int [n];
	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++;
	}

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

int main()
{
	int i1, i2, **r;

	r = new int * [7];
	for (i1 = 0; i1 < 7; i1++) {
		r[i1] = new int [7];
		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;

	dynamic(7, r);

	return 0;
}