横型探索（最短経路）

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

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

	q.push(pair<int, int>(0, 0));
	while (!q.empty()) {
		k = q.front().first;
		v = q.front().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;

	width(7, r, rd);

	return 0;
}

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

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

void width(int n, int **r, int *rd, int d, int m, int *nd)
{
	int i1, i2, k, r1, m1, *nd1 = new int [n];

	m1 = 0;
	for (i1 = 0; i1 < m; i1++) {
		k = nd[i1];
		for (i2 = 0; i2 < n; i2++) {
			if (r[k][i2] >= 0) {
				r1 = rd[k] + r[k][i2];
				if (rd[i2] < 0 || r1 < rd[i2]) {
					rd[i2]  = r1;
					nd1[m1] = i2;
					m1++;
				}
			}
		}
	}
	if (m1 > 0)
		width(n, r, rd, d+1, m1, nd1);

	delete [] nd1;
}

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

	nd = new int [7];
	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;
	}
	nd[0]   = 0;
	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;

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

	return 0;
}