최단경로 알고리즘

최단경로 알고리즘이란 그래프에서 노드간의 최단경로를 찾는 알고리즘이다.

대표적인 최단경로 알고리즘

1. BFS
2. 다익스트라
3. 벨만포드
4. 플로이드 와샬

다음 표는 상황에 따라 어떤 알고리즘을 선택해야 하는지에 대한 표이다.

		단일 노드 - 단일 노드	모든 노드 쌍
Edge에 weight 없음		BFS	플로이드 와샬 알고리즘
Edge에 weight 있음	음수 weight 있음	벨만 포드 알고리즘
	음수 weight 없음	다익스트라 알고리즘

(출처. https://shnoh.tistory.com/15)

 

다익스트라 알고리즘

한 정점 A에서 다른 정점으로 가는 촤단경로를 구할 때 사용.
가중치는 0 또는 양수만 가능하다.
그리디를 이용한 알고리즘

O(V^2)
O((V+E)logV) // 우선순위 큐를 사용했을때

    private void dijkstra(int V, int E, ArrayList<ArrayList<Node>> graph){

        int[] distance = new int[V+1];
        boolean[] visited = new boolean[V+1];

        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[1] = 0;
        visited[1] = true;

        for (Node node : graph.get(1)) {
            distance[node.e] = node.weight;
        }

        int minIdx,min;
        int sum=0;

        for (int i = 1; i < V-1; i++) {

            minIdx = 0;
            min = Integer.MAX_VALUE;

            //방문 안한 노드 중 distance값이 가장 작은거 찾기
            for (int j = 0; j < distance.length; j++) {
                if(visited[j])  continue;
                if(min>distance[j]){
                    min = distance[j];
                    minIdx = j;
                }
            }

            visited[minIdx] = true;

            //찾은 노드의 인접으로 distance 갱신
            for (Node node : graph.get(minIdx)) {
                if(visited[node.e]) continue;
                distance[node.e] = Math.min(distance[minIdx]+node.weight,distance[node.e]);
            }

        }

        System.out.println(Arrays.toString(distance));

    }

 

벨만포드 알고리즘

한 정점 A에서 다른 정점으로 가는 최단경로를 구할 때 사용
가중치는 음수, 0, 양수 모두 가능
DP를 이용한 알고리즘
음의 사이클이 생기면 음의 무한이 되기 때문에 사이클이 발생하는지 체크 필수!

O(V^3) = O(VE) //평균적으로 간선의 개수는 노드의 제곱으로 본다.

    private void bellman(int V, int E, int[][] edges){
        int[] distance = new int[V+1];
        boolean[] visited = new boolean[V+1];
        boolean isUpdated;
        for (int i = 1; i <= V; i++) {
            distance[i] = INF;
        }

        distance[1] = 0;
        for (int i = 1; i <= V; i++) { // 경로 길이 V-1, V가 되면 사이클 생긴거
            isUpdated = false;
            for (int[] edge : edges) {
                if(distance[edge[1]]>distance[edge[0]]+edge[2]){
                    distance[edge[1]]=distance[edge[0]]+edge[2];
                    isUpdated = true;
                    if(i==V){
                        System.out.println("음의 사이클 발생!!!");
                        return;
                    }
                }
            }
            if(!isUpdated)  break; //아무런 변화 없으므로 조기 종료!
        }

        System.out.println(Arrays.toString(distance));

    }

 

플로이드 와샬 알고리즘

모든 정점간의 최단경로를 구할 때 사용
가중치는 음수, 0, 양수 모두 가능
DP를 이용한 알고리즘
음의 사이클 체크 필수

O(V^3)

    
    private void floid(int V, int E, ArrayList<ArrayList<Node>> graph){
        int[][] distance = new int[V+1][V+1];

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                distance[i][j] = INF;
            }
        }

        for (int i = 1; i <=V; i++) {
            for (Node node : graph.get(i)) {
                distance[i][node.e] = node.weight;
            }
        }

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 1; k <= V; k++) {
                    if(distance[j][i]!=INF && distance[i][k]!=INF)
                        distance[j][k] = Integer.min(distance[j][k],distance[j][i]+distance[i][k]);
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                System.out.print(distance[i][j]+" ");
            }
            System.out.println();
        }

    }

 

전체 코드

package shortest_path;  

import java.util.ArrayList;  
import java.util.Arrays;  

public class Shortest_path {  
private final int INF = Integer.MAX_VALUE;  
    static class Node{  
        int e,weight;  
        public Node(){  
        }  
        public Node(int e, int weight){  
            this.e = e;  
            this.weight = weight;  
        }  
    }  
    public static void main(String[] args) {  
        int V = 4, E = 7;  
        //int V = 8,E=11;  
  int[][] edges  = {{1,2,4},{1,3,1},{2,3,2},{2,4,1},{3,2,1},{4,1,5},{4,3,5}};  
        //int[][] edges = {{1,2,3},{1,5,4},{1,4,4},{2,3,2},{3,4,1},{4,5,2},{5,6,4},{4,7,6},{7,6,3},{3,8,3},{6,8,2}};  

  ArrayList<ArrayList<Node>> graph = new ArrayList<>();  

        for (int i = 0; i <= V; i++) {  
            graph.add(new ArrayList<>());  
        }  

        for (int[] edge : edges) {  
            graph.get(edge[0]).add(new Node(edge[1],edge[2]));  
        }  

        System.out.println("1에서 출발하는 다익스트라");  
        new Shortest_path().dijkstra(V,E,graph);  

        System.out.println("플로이드와샬");  
        new Shortest_path().floid(V,E,graph);  

        System.out.println("1에서 출발하는 벨만포드");  
        new Shortest_path().bellman(V,E,edges);  
    }  

    private void bellman(int V, int E, int[][] edges){  
        int[] distance = new int[V+1];  
        boolean[] visited = new boolean[V+1];  
        boolean isUpdated;  
        for (int i = 1; i <= V; i++) {  
            distance[i] = INF;  
        }  

        distance[1] = 0;  
        for (int i = 1; i <= V; i++) { // 경로 길이 V-1, V가 되면 사이클 생긴거  
  isUpdated = false;  
            for (int[] edge : edges) {  
                if(distance[edge[1]]>distance[edge[0]]+edge[2]){  
                    distance[edge[1]]=distance[edge[0]]+edge[2];  
                    isUpdated = true;  
                    if(i==V){  
                        System.out.println("음의 사이클 발생!!!");  
                        return;  
                    }  
                }  
            }  
            if(!isUpdated)  break; //아무런 변화 없으므로 조기 종료!  
  }  

        System.out.println(Arrays.toString(distance));  

    }  
    private void floid(int V, int E, ArrayList<ArrayList<Node>> graph){  
        int[][] distance = new int[V+1][V+1];  

        for (int i = 1; i <= V; i++) {  
            for (int j = 1; j <= V; j++) {  
                distance[i][j] = INF;  
            }  
        }  

        for (int i = 1; i <=V; i++) {  
            for (Node node : graph.get(i)) {  
                distance[i][node.e] = node.weight;  
            }  
        }  

        for (int i = 1; i <= V; i++) {  
            for (int j = 1; j <= V; j++) {  
                for (int k = 1; k <= V; k++) {  
                    if(distance[j][i]!=INF && distance[i][k]!=INF)  
                        distance[j][k] = Integer.min(distance[j][k],distance[j][i]+distance[i][k]);  
                }  
            }  
        }  

        for (int i = 1; i <= V; i++) {  
            for (int j = 1; j <= V; j++) {  
                System.out.print(distance[i][j]+" ");  
            }  
            System.out.println();  
        }  

    }  

    private void dijkstra(int V, int E, ArrayList<ArrayList<Node>> graph){  


        int[] distance = new int[V+1];  
        boolean[] visited = new boolean[V+1];  

        for (int i = 0; i < distance.length; i++) {  
            distance[i] = Integer.MAX_VALUE;  
        }  
        distance[1] = 0;  
        visited[1] = true;  

        for (Node node : graph.get(1)) {  
            distance[node.e] = node.weight;  
        }  

        int minIdx,min;  
        int sum=0;  

        for (int i = 1; i < V-1; i++) {  

            minIdx = 0;  
            min = Integer.MAX_VALUE;  

            //방문 안한 노드 중 distance값이 가장 작은거 찾기  
  for (int j = 0; j < distance.length; j++) {  
                if(visited[j])  continue;  
                if(min>distance[j]){  
                    min = distance[j];  
                    minIdx = j;  
                }  
            }  

            visited[minIdx] = true;  

            //찾은 노드의 인접으로 distance 갱신  
  for (Node node : graph.get(minIdx)) {  
                if(visited[node.e]) continue;  
                distance[node.e] = Math.min(distance[minIdx]+node.weight,distance[node.e]);  
            }  

        }  

        System.out.println(Arrays.toString(distance));  

    }  

}