MyDjikstra

Mydjistra.java

package Main;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class MyDijkstra {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [][] e = {{0,1,20},{0,2,50},{1,0,20},{1,3,30},{2,1,5},{3,1,30},{3,2,5}};
		int [][] matrix = makeAdjMatrix(new int[] {0,1,2,3}, e);
		printMatrix(matrix);
		List<Integer> visited = new ArrayList<Integer>();
		Map<Integer,List<Integer>> route = new HashMap<Integer,List<Integer>>();
		int [] distance = new int[4];
		int start = 3, end = 1, baseDist = 0;
		int current = start;
		
		
		for (int i = 0; i < distance.length; i++) distance[i] = 1001;
		
		distance[start] = 0;
		route.put(start, new ArrayList<Integer>());
		route.get(start).add(start);
		
		while(true) {
			//System.out.println(current);
			baseDist = distance[current];
			visited.add(current);
			for(int i = 0; i < matrix[current].length; i++) {
				if (visited.contains(i)) continue;
				int dist = matrix[current][i];
				if ((baseDist+dist) < distance[i]) {
					distance[i] = baseDist+dist;
					List<Integer> newRoute = new ArrayList<Integer>();
					for (Integer nr: route.get(current)) {
						newRoute.add(nr);
					}
					newRoute.add(i);
					route.put(i, newRoute);
				}
			}
				
			int minDist = 1001;
			for (int i = 0; i < distance.length; i++) {
				if (visited.contains(i)) continue;
				if (distance[i] < minDist) {
					minDist = distance[i];
					current = i;
				}
			}
			
			if (visited.contains(end)) break;
		}
		for (Integer p : route.get(end)) {
			System.out.println(p);
		}
		System.out.println(distance[end]);
	}
	
	public static int[][] makeAdjMatrix(int []v, int[][] e) {
		int [][] matrix = new int [v.length][v.length];
		for (int i = 0; i < matrix.length; i++)
			for (int j = 0; j < matrix[i].length; j++) 
				matrix[i][j] = (i == j)?0:1001;
				
		
		for (int i = 0; i < e.length; i++) {
			matrix[e[i][0]][e[i][1]] = e[i][2];
		}
		return matrix;
	}
	
	public static void printMatrix(int [][] m) {
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[i].length; j++) {
				System.out.print(m[i][j] + "     ");
			}
			System.out.println();
		}
	}

}