최단 경로 찾기 알고리즘 (벨만-포드, 플로이드-워샬)

아래 두 알고리즘은 음의 가중치가 존재할 때 사용된다.

음의 사이클이 존재한다면 작동하지 않는다.

벨만-포드 알고리즘

• 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는데 사용

입력값: (G,r) : 가중치가 표시되어있는 V*V 2차원 배열(그래프)G, 시작 정점 r

결과값: dist : 정점r 부터의 각 정점까지의 최단거리 배열

시간복잡도: O(VE) // V: 정점 수, E:간선 수

 

알고리즘이 간선의 수 만큼 반복하는 것이므로

그래프(V*V의 2차원배열)에서 부터 정점, 간선의 정보를 추출해야한다. 

// 모든 정점을 V - 1번 relaxation합니다.
// 그래프에서 한 노드에서 다른 노드로 가는 최단 경로가 모든 노드를 통과하는 경우가 있을 수 있기 때문
//ex) A -- B -- C -- D   A에서 D로 가려면 모든 노드를 거치게 됨

for (int i = 1; i < V; ++i) {
    for (int j = 0; j < E; ++j) {
        int u = graph.edge[j].src; //src: 간선 edge[j]의 출발 노드
        int v = graph.edge[j].dest;//dest: 간선 edge[j]의 도착 노드
        int weight = graph.edge[j].weight; //src -> dest 거리
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
            dist[v] = dist[u] + weight;
    }
}
//weight: u -> v 거리
//dist[u] + weight: r -> u -> v 의 거리
//dist[v]: r -> v 의 거리
//ruv와 rv를 비교해서 짧은것으로 바꿔준다.

public class Edge {
    int src, dest, weight;
    Edge() {
        src = dest = weight = 0;
    }
};

public class BellmanFord {

    int V, E;
    Edge edge[];

    // 생성자
    BellmanFord(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    // 벨만 포드 알고리즘 구현
    void BellmanFord(BellmanFord graph, int r) {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

        // 모든 거리를 무한대로 초기화
        for (int i = 0; i < V; ++i)
            dist[i] = Integer.MAX_VALUE;

        // 시작 정점의 거리를 0으로 초기화
        dist[r] = 0;

        // 모든 정점을 V - 1번 relaxation합니다.
        for (int i = 1; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }

        // 음수 사이클 검사
        // V-1번 반복했는데도 더 줄어들 여지가 있다는 것은 음의 사이클이 존재한다는 뜻
        for (int j = 0; j < E; ++j) {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dest;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
        printArr(dist, V);
    }

    // 결과 출력
    void printArr(int dist[], int V) {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "\t\t" + dist[i]);
    }
}

public static void main(String[] args) {
    int V = 5;  // 노드 수
    int E = 8;  // 엣지 수

    BellmanFord graph = new BellmanFord(V, E);

    // 그래프 edge를 생성합니다.
    // edge(src, dest, weight)
    graph.edge[0] = new Edge(0, 1, -1);
    graph.edge[1] = new Edge(0, 2, 4);
    graph.edge[2] = new Edge(1, 2, 3);
    graph.edge[3] = new Edge(1, 3, 2);
    graph.edge[4] = new Edge(1, 4, 2);
    graph.edge[5] = new Edge(3, 2, 5);
    graph.edge[6] = new Edge(3, 1, 1);
    graph.edge[7] = new Edge(4, 3, -3);

    graph.BellmanFord(graph, 0);
}

플로이드-워샬 알고리즘

• 그래프 내의 모든 노드 쌍 사이의 최단 거리를 찾는데 사용

입력값: G : 가중치가 표시되어있는 V*V 2차원 배열(그래프)

결과값: dist : 각 정점간의 최단거리가 계산된 V*V 2차원 배열

시간복잡도: O(V^3)

//i: 출발 정점, j: 도착 정점, k: 경유 정점
//dist[i][j]: 원래의 저장되어있던 i->j의 거리
//dist[i][k] + dist[k][j]: i에서 k를 경유해서 j로 도착하는 거리
//가 더 짧다면 교체
//k를 0부터 V까지 순회하며 경유하는 모든 경우를 확인한다.

for (k = 0; k < V; k++) {
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][k] + dist[k][j] < dist[i][j])
            dist[i][j] = dist[i][k] + dist[k][j];
        }
    }
}

public class FloydWarshall {
    final static int INF = 99999, V = 3;

    void floydWarshall(int[][] graph) {
        int[][] dist = new int[V][V];
        int i, j, k;

        for (i = 0; i < V; i++)
            for (j = 0; j < V; j++)
                dist[i][j] = graph[i][j];

        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

        printSolution(dist);
    }

    void printSolution(int[][] dist) {
        System.out.println("Following matrix shows the shortest " +
                "distances between every pair of vertices");
        for (int i=0; i<V; ++i) {
            for (int j=0; j<V; ++j) {
                if (dist[i][j]==INF)
                    System.out.print("INF ");
                else
                    System.out.print(dist[i][j]+"   ");
            }
            System.out.println();
        }
    }

    public static void main (String[] args) {
        int[][] graph = {
                {0, 3, -1},
                {3, 0, 3},
                {3, -1, 0},
        };
        FloydWarshall a = new FloydWarshall();

        a.floydWarshall(graph);
    }
}

//결과값의 대각선 위치(자기 자신을 가리키는 위치: 0이어야 한다)에 음수가 존재한다면 음의 사이클이 존재한다는 뜻이다.

for (int i = 0; i < V; i++) {
    if (dist[i][i] < 0) {
        System.out.println("The graph contains a negative cycle");
        return;
    }
}
System.out.println("The graph doesn't contain a negative cycle");