Dijkstra（最短経路）

/****************************/
/* Dijkstra（最短経路）     */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

class Comp implements Comparator <Net> {
	public int compare (Net n1,  Net n2)
	{
		if (n1.r == n2.r)
			return  n1.node - n2.node;
		else
			return  n1.r - n2.r;
	}
}

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

class Search
{
	/********************************************/
	/* Dijkstra（最短経路）                     */
	/*      n : ノードの数                      */
	/*          　ノード0:スタート              */
	/*          　ノード(n-1):ゴール            */
	/*      r : ノード間の距離                  */
	/*      rd : 現時点におけるノードまでの距離 */
	/*      used : 距離が確定したか否か         */
	/********************************************/
	static void width(int n, int r[][], int rd[], boolean used[])
	{
		int i1, k, v, r1, node = 1;
		Net net;
		Comparator<Net> cp = new Comp();
		TreeSet <Net> s = new TreeSet <Net> (cp);

		s.add(new Net(0, 0));
		while (!s.isEmpty()) {
			net = s.first();
			k   = net.node;
			v   = net.r;
			if (!used[k]) {
					// 先頭のノードから到達可能なノードをセットに追加
					//　　・距離が決定しているノードは除く
					//　　・既にノードまでの距離が計算済みであり，その距離が
					//　　　今回計算した距離よりも短い場合は距離を修正して追加
				used[k] = true;
				for (i1 = 0; i1 < n; i1++) {
					if (!used[i1] && r[k][i1] >= 0) {
						r1 = v + r[k][i1];
						if (rd[i1] < 0 || r1 < rd[i1]) {
							s.add(new Net(i1, r1));
							rd[i1] = r1;
							node++;
						}
					}
				}
			}
			s.remove(net);
		}

		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];
		boolean used[] = new boolean [7];

		for (i1 = 0; i1 < 7; i1++) {
			used[i1] = false;
			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, used);
	}
}

-----------------TreeSet を使用しない方法----------------

/****************************/
/* Dijkstra（最短経路）     */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

class Search
{
	/********************************************/
	/* Dijkstra（最短経路）                     */
	/*      n : ノードの数                      */
	/*          　ノード0:スタート              */
	/*          　ノード(n-1):ゴール            */
	/*      r : ノード間の距離                  */
	/*      rd : 現時点におけるノードまでの距離 */
	/*      used : 距離が確定したか否か         */
	/********************************************/
	static void Dijkstra(int n, int r[][], int rd[], boolean used[])
	{
		int i1, r1, node = 1, nx, next = 0;

		while (next >= 0) {
					// 先頭のノードから到達可能なノードを調べる
					//　　・距離が決定しているノードは除く
					//　　・既にノードまでの距離が計算済みであり，その距離が
					//　　　今回計算した距離よりも短い場合は距離を修正して追加
			nx       = next;
			next     = -1;
			used[nx] = true;
			for (i1 = 0; i1 < n; i1++) {
				if (!used[i1]) {
					if (r[nx][i1] >= 0) {
						r1 = rd[nx] + r[nx][i1];
						if (rd[i1] < 0 || r1 < rd[i1]) {
							rd[i1] = r1;
							node++;
						}
					}
					if (next < 0 || rd[i1] >= 0 && rd[i1] < rd[next])
						next = i1;
				}
			}
		}

		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];
		boolean used[] = new boolean [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.Dijkstra(7, r, rd, used);

	}
}