Implementation of Dijkstra Shortest Paths in Java.

ShortestPaths.java

package kr.opid.algorithm;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author Yeong-jun
 *
 */
public class ShortestPaths {
	public static void main(String[] args) {
		int m = Integer.MAX_VALUE;
		int[][] matrix = new int[][] { 
			{ 0, 3, 1, m, m, 1 }, 
			{ m, 0, m, m, m, 3 }, 
			{ m, m, 0, m, m, m },
			{ m, m, m, 0, 2, m }, 
			{ m, m, m, m, 0, m }, 
			{ m, 1, m, 2, 6, 0 } };

		Dijkstra s = new Dijkstra();
		s.dijkstra(matrix, 0);
		
		System.out.println(s.getPathList(1));
		System.out.println(s.getPathList(2));
		System.out.println(s.getPathList(3));
		System.out.println(s.getPathList(4));
		System.out.println(s.getPathList(5));

	}
}

class Dijkstra {
	boolean[] mVisit;
	long[] mDist;
	int[] mPath;
	int mStart;

	/**
	 * 딕스트라 최단경로
	 * 
	 * @param st
	 * @param end
	 */
	void dijkstra(int[][] matrix, int st) {
		int size = matrix.length;

		boolean[] visit = new boolean[size];
		long[] dist = new long[size];
		int[] path = new int[size];

		double tmpDist = 0.0;
		int tmpIdx = 0;

		// Initialize
		for (int i = 0; i < size; i++) {
			dist[i] = Integer.MAX_VALUE;
			visit[i] = false;
			path[i] = -1;
		}

		// start point distance is 0.
		dist[st] = 0;

		for (int i = 0; i < size; i++) {
			tmpDist = Integer.MAX_VALUE;
			// 가장 짧은 곳 선택
			for (int j = 0; j < size; j++) {
				if (visit[j] == false && dist[j] < tmpDist) {
					tmpIdx = j;
					tmpDist = dist[j];
				}
			}

			// 선택한 곳 방문 체크
			visit[tmpIdx] = true;

			// 짧은 곳이 없으면 종료
			if (dist[tmpIdx] == Integer.MAX_VALUE) {
				break;
			} else {
				// 비교
				for (int j = 0; j < size; j++) {
					if (dist[j] > dist[tmpIdx] + matrix[tmpIdx][j]) {
						dist[j] = dist[tmpIdx] + matrix[tmpIdx][j];
						path[j] = tmpIdx;
					}
				}
			}
		}

		mStart = st;
		mVisit = visit;
		mDist = dist;
		mPath = path;
	}

	/**
	 * 최단경로를 리스트로 변경해서 반환
	 * 
	 * @return
	 */
	ArrayList<Integer> getPathList(int end) {
		ArrayList<Integer> resultList = new ArrayList<>();
		Stack<Integer> stack = new Stack<>();
		int pointer = end;

		while (true) {
			if (mPath[pointer] != -1 && mStart != end) {
				stack.push(pointer);
				pointer = mPath[pointer];
			} else {
				stack.push(mStart);
				break;
			}
		}

		while (!stack.empty())
			resultList.add(stack.pop());

		return resultList;
	}
}