横型探索（最短経路）

/****************************/
/* 横型探索（最短経路）     */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

class Pair
{
	int node;   // ノード番号
	int r;   // スタートからの距離
	Pair (int node1, int r1)
	{
		node = node1;
		r    = r1;
	}
}

class Search
{
	/********************************************/
	/* 横型探索（最短経路）                     */
	/*      n : ノードの数                      */
	/*          　ノード0:スタート              */
	/*          　ノード(n-1):ゴール            */
	/*      r : ノード間の距離                  */
	/*      rd : 現時点におけるノードまでの距離 */
	/********************************************/
	static void width(int n, int r[][], int rd[])
	{
		int i1, k, v, r1, node = 1;
		Pair pair;
		ArrayDeque <Pair> q = new ArrayDeque <Pair> ();

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

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

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

		for (i1 = 0; i1 < 7; i1++) {
			rd[i1] = -1;
			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;

		Search.width(7, r, rd);
	}
}

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

/****************************/
/* 横型探索（最短経路）     */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;

class Search
{
	/********************************************/
	/* 横型探索（最短経路）                     */
	/*      n : ノードの数                      */
	/*          　ノード0:スタート              */
	/*          　ノード(n-1):ゴール            */
	/*      r : ノード間の距離                  */
	/*      rd : 現時点におけるノードまでの距離 */
	/*      d : 深さ                            */
	/*      m : 深さdにあるノードの数           */
	/*      nd : 深さdにあるノード              */
	/********************************************/
	static 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);
	}
}

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

		for (i1 = 0; i1 < 7; i1++) {
			rd[i1] = -1;
			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;

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