縦型探索（最短経路）

/****************************/
/* 縦型探索（最短経路）     */
/*      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 depth(int n, int r[][], int rd[])
	{
		int i1, k, v, r1, node = 1;
		Pair pair;
		Stack <Pair> q = new Stack <Pair> ();

		q.push(new Pair(0, 0));
		while (!q.isEmpty()) {
			pair = q.pop();
			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.push(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.depth(7, r, rd);
	}
}

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

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

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

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.depth(7, r, rd, 1, 0);
		System.out.printf("最短距離： %d\n", rd[6]);
	}
}