MyDijkstraTest

public class MyDijkstraTest {

	/**
	 * @param args
	 */
	public static int U = 99999999;

	public static void main(String[] args) {
		int[][] graph = { { 0, 50, U, 80, U }, { U, 0, 60, 90, U },
				{ U, U, 0, U, 40 }, { U, U, 20, 0, 70 }, { U, 50, U, U, 0 } };
		int start = 0;
		Path2Len[] path2LenArray = getShorestPath(graph, start);
		for (int i = 0; i < path2LenArray.length; i++) {
			Path2Len path2Len = path2LenArray[i];
			int lastVetrex = path2Len.lastVetrex;
			System.out.print("from " + start + " to " + i + " length:"
					+ path2Len.len + ", path: " + i + " <-- " + lastVetrex);

			while (lastVetrex != start) {
				lastVetrex = path2LenArray[lastVetrex].lastVetrex;
				System.out.print(" <--" + lastVetrex);

			}
			System.out.println();
		}

	}

	public static Path2Len[] getShorestPath(int[][] graph, int start) {
		int N = graph.length;
		Path2Len[] path2LenArray = new Path2Len[N];
		boolean[] visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			Path2Len path2Len = new Path2Len();
			path2Len.lastVetrex = start;
			path2Len.len = graph[start][i];
			path2LenArray[i] = path2Len;
			visited[i] = false;
			System.out.println("init " + start + " --> " + i + ":    " + path2Len.len);
		}

		visited[start] = true;

		for (int count = 0; count < N - 1; count++) {
			int minIndex = -1;
			int minLen = U;
			for (int i = 0; i < N; i++) {
				if (!visited[i] && path2LenArray[i].len < minLen) {
					minLen = path2LenArray[i].len;
					minIndex = i;
				}
			}
			if (minLen == U) {
				break;
			}
			visited[minIndex] = true;

			for (int i = 0; i < N; i++) {
				if (!visited[i]
						&& graph[minIndex][i] < U
						&& path2LenArray[minIndex].len + graph[minIndex][i] < path2LenArray[i].len) {
					path2LenArray[i].len = path2LenArray[minIndex].len
							+ graph[minIndex][i];
					path2LenArray[i].lastVetrex = minIndex;
					System.out.println("update " + start + " --> " + i + " via "
							+ minIndex + ":   " + path2LenArray[i].len);
				}
			}
		}

		return path2LenArray;
	}

}

class Path2Len {
	public int lastVetrex;
	public int len;
}

输出：

init 0 --> 0:    0
init 0 --> 1:    50
init 0 --> 2:    99999999
init 0 --> 3:    80
init 0 --> 4:    99999999
update 0 --> 2 via 1:   110
update 0 --> 2 via 3:   100
update 0 --> 4 via 3:   150
update 0 --> 4 via 2:   140
from 0 to 0 length:0, path: 0 <-- 0
from 0 to 1 length:50, path: 1 <-- 0
from 0 to 2 length:100, path: 2 <-- 3 <--0
from 0 to 3 length:80, path: 3 <-- 0
from 0 to 4 length:140, path: 4 <-- 2 <--3 <--0