Part2. 8-5 최단거리 (다익스트라 알고리즘)

다익스트라 알고리즘 : 시작노드가 정해져 있고 , 시작노드에서 모든 노드로 가는 데 걸리는 최단거리를 구하는 알고리즘

 

 

여기에서 y1 의 의미는  기준노드 0에서 1까지의 거리를 말한다

C1,2 의 의미는  1번 노드에서 2번 노드까지의 거리를 말한다.

 

 

 

 

class MyGraph{
    private int count;   //노드 수           
    private int[][] vertexMatrix;  // matrix로 그래프 표시
    private int[] distance;        // 특정 노드에 대한 각 노드의 최단 거리
    private boolean[] visited;     // 노드 방문 여부 저장
    private static int UNLIMIT = 999999999;  // 초기값 (무한대)
    
    public MyGraph(int count){
        this.count = count;
        vertexMatrix = new int[count][count];
        distance = new int[count];
        visited = new boolean[count];
         
    }
    public void addEdges(int from, int to, int weight){
    	vertexMatrix[from][to] = weight;
    	vertexMatrix[to][from] = weight;
    }
 
    public void calcShotestPath(int from){
         
        for(int i=0;i<count;i++){
            distance[i] = UNLIMIT;           // 거리 모두 무한대로 초기화
        }
        
        visited[from] = true;            // 시작노드 방문 처리 (from은 함수 매개변수)
        distance[from] = 0;              // 본인의 거리니까 0으로 초기화
                                                      
        for(int i= 0; i<count; i++){       // 시작노드를 기준으로 distance갱신
            if(vertexMatrix[from][i] !=0){
                distance[i] = vertexMatrix[from][i];
            }
        }
         
        
        for(int k =0; k<count-1; k++){    // 시작 노드는 제외한 모든 노드 : count - 1

            int min=UNLIMIT;
            int minIndex= -1;
            
            for(int i = 0; i< count ;i++){
                if(!visited[i] && distance[i]!=UNLIMIT){  // **** 방문하지 않았고(중간 거쳐가는 노드로 선택되지 않았고) , 노드가 이어져 있으면
                    if(distance[i] < min ){              
                        min = distance[i];
                        minIndex = i;                  // 이어진 노드 중 최소 거리 노드 찾기
                    }
                }
            }
            
            visited[minIndex] = true;                  // minIndex가 거쳐 가는 노드가 된다.
            for(int i=0; i<count; i++){              // 다익스트라 알고리즘
                if(!visited[i] && vertexMatrix[minIndex][i]!=0){   // ** 거쳐 가는 노드의 인접 노드들이 방문하지 않았을 때
                    if(distance[i] > distance[minIndex] + vertexMatrix[minIndex][i]){  // i의 원래 거리가 (거쳐 가는 노드까지의 거리 + 거쳐 가는 노드에서 i까지의 거리) 보다 크면 
                        distance[i] = distance[minIndex] + vertexMatrix[minIndex][i];  // 더 작은 거리로 갱신
                    }
                }
            }
        }
    }
    
    public void showDistance(int from) {
    	
    	for(int i = 0; i<count; i++) {
    		
    		System.out.println(from + " 노드로부터 " + i + " 노드의 최단 거리는 : " + distance[i]);
    	}
    }
}


public class ShortestPath {

	public static void main(String[] args) {
		MyGraph graph = new MyGraph(6);
		graph.addEdges(0, 1, 1);
		graph.addEdges(0, 2, 4);
		graph.addEdges(1, 2, 2);
		graph.addEdges(2, 3, 1);
		graph.addEdges(3, 4, 8);
		graph.addEdges(3, 5, 3);
		graph.addEdges(4, 5, 4);

		graph.calcShotestPath(0);
		graph.showDistance(0);

	}
}