縦型探索（最短経路）

/********************************************/
/* 縦型探索（最短経路）                     */
/*      n : ノードの数                      */
/*          　ノード0:スタート              */
/*          　ノード(n-1):ゴール            */
/*      r : ノード間の距離                  */
/*      rd : 現時点におけるノードまでの距離 */
/*           coded by Y.Suganuma            */
/********************************************/
#include <stdio.h>
#include <stack>
using namespace std;

void depth(int n, int **r, int *rd)
{
	int i1, k, v, r1, node = 1;
	stack<pair<int, int> > q;

	q.push(pair<int, int>(0, 0));
	while (!q.empty()) {
		k = q.top().first;
		v = q.top().second;
		q.pop();
					// 先頭のノードから到達可能なノードをスタックに追加
					// （既にノードまでの距離が計算済みであり，その
					//   距離が今回計算した距離よりも短い場合は除く)
		for (i1 = 0; i1 < n; i1++) {
			if (r[k][i1] >= 0) {
				r1 = v + r[k][i1];
				if (rd[i1] < 0 || r1 < rd[i1]) {
					q.push(pair<int, int>(i1, r1));
					rd[i1] = r1;
					node++;
				}
			}
		}
	}

	printf("展開したノード数： %d，　最短距離： %d\n", node, rd[n-1]);
}

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

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

	depth(7, r, rd);

	return 0;
}

----------------再帰関数の利用----------------

/********************************************/
/* 縦型探索（最短経路）                     */
/*      n : ノードの数                      */
/*          　ノード0:スタート              */
/*          　ノード(n-1):ゴール            */
/*      r : ノード間の距離                  */
/*      rd : 現時点におけるノードまでの距離 */
/*      d : 深さ                            */
/*      now : 現在のノード                  */
/*           coded by Y.Suganuma            */
/********************************************/
#include <stdio.h>

void depth(int n, int **r, int *rd, int d, int now)
{
	int i1, r1;

	for (i1 = 0; i1 < n; i1++) {
		if (r[now][i1] >= 0) {
			r1 = rd[now] + r[now][i1];
			if (rd[i1] < 0 || r1 < rd[i1]) {
				rd[i1] = r1;
				depth(n, r, rd, d+1, i1);
			}
		}
	}
}

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

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

	depth(7, r, rd, 1, 0);
	printf("最短距離： %d\n", rd[6]);

	return 0;
}