algorithm
Dijkstra의 알고리즘

Dijkstra의 최단 경로 알고리즘

진행하기 전에, Adjacency Matrix와 BFS에 대한 간단한 생각을하는 것이 좋습니다.

Dijkstra의 알고리즘 은 단일 소스 최단 경로 알고리즘으로 알려져 있습니다. 그래프에서 노드 간의 최단 경로를 찾는 데 사용되며 예를 들어 도로 네트워크를 나타낼 수 있습니다. Edsger W. Dijkstra 에 의해 1956 년에 잉태되었고 3 년 후에 출판되었습니다.

Breadth First Search (BFS) 검색 알고리즘을 사용하여 최단 경로를 찾을 수 있습니다. 이 알고리즘은 잘 작동하지만 문제는 각 경로를 가로 지르는 비용이 같다고 가정합니다. 즉, 각 에지의 비용이 동일하다는 것을 의미합니다. Dijkstra의 알고리즘은 각 경로의 비용이 같지 않은 최단 경로를 찾는 데 도움이됩니다.

처음에는 Dijkstra 알고리즘을 작성하기 위해 BFS를 수정하는 방법을 살펴본 다음 우선 순위 대기열을 추가하여 완전한 Dijkstra 알고리즘으로 만듭니다.

소스로부터 각 노드까지의 거리가 d [] 배열로 유지된다고 가정 해보자. 에서와 같이, d [3] 은 소스 로부터 노드 3 에 도달하기 위해 d [3] 시간이 소요됨을 나타냅니다. 거리를 모를 경우 무한대 를 d에 저장 합니다 [3] . 또한 비용 [u] [v] 를 uv 의 비용으로 나타냅니다. 즉 u 노드에서 v 노드로 이동하는 데 비용 이 소요됩니다.

Edge Relaxation을 이해해야합니다. 예를 들어, 집에서 출처를 말하자면 A 장소로 이동하는 데 10 분이 걸립니다. 그리고 B 장소로 가는데 25 분이 걸립니다. 우리는,

d[A] = 10
d[B] = 25

이제 A 지점에서 B 지점으로 이동하는 데 7 분이 걸린다고 가정 해 봅시다.

cost[A][B] = 7

그런 다음 우리는 10 + 7 = 17분 대신 25 분 정도 걸립니다 B를 배치하는 것, 장소 A에서 다음 소스의 장소로 이동하여 소스에서 B 장소로 이동 할 수 있습니다. 그래서,

d[A] + cost[A][B] < d[B]

그런 다음,

d[B] = d[A] + cost[A][B]

이를 이완이라고합니다. 노드 u 에서 노드 v 로 갈 것이고 d [u] + cost [u] [v] <d [v] 라면 d [v] = d [u] + cost [u] [v]를 갱신 할 것이다.

BFS에서 노드를 두 번 방문 할 필요가 없었습니다. 노드가 방문되었는지 아닌지 만 확인했습니다. 방문하지 않은 경우 노드를 대기열에 넣고 방문한 것으로 표시하고 거리를 1 씩 증가시킵니다. Dijkstra에서는 대기열에있는 노드를 밀어 넣을 수 있으며 방문한 노드로 업데이트하는 대신 새 가장자리를 완화 하거나 업데이트 할 수 있습니다. 한 가지 예를 살펴 보겠습니다.

노드 1 이 소스 라고 가정 해 봅시다. 그때,

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

우리는 거리를 아직 모르기 때문에 d [2], d [3] 및 d [4] 를 무한대로 설정 합니다. 그리고 소스 의 거리는 물론 0 입니다. 이제 소스 에서 다른 노드로 이동하여 업데이트 할 수 있으면 대기열에서 해당 노드를 푸시합니다. 예를 들어 우리는 가장자리 1-2를 횡단합니다. d [1] + 2 <d [2] 로서 d [2] = 2가된다 . 비슷하게, 우리는 d [3] = 5가 되는 가장자리 1-3 을 가로 질러 갈 것입니다.

우리는 5 가 노드 3 에 가기 위해 교차 할 수있는 최단 거리가 아니라는 것을 분명히 알 수 있습니다. 따라서 BFS와 같이 노드를 한 번만 탐색하면 여기에서 작동하지 않습니다. 에지 2-3을 사용하여 노드 2 에서 노드 3으로 이동하면 d [3] = d [2] + 1 = 3을 업데이트 할 수 있습니다. 따라서 한 노드가 여러 번 업데이트 될 수 있음을 알 수 있습니다. 몇 번이나 물어봐? 노드를 갱신 할 수있는 최대 = 수는 노드의 학위의 수입니다.

임의의 노드를 여러 번 방문하기위한 가상 코드를 봅시다. 우리는 단순히 BFS를 수정합니다 :

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

이것은 소스에서 모든 노드의 최단 경로를 찾는 데 사용될 수 있습니다. 이 코드의 복잡성은 그리 좋지 않습니다. 여기 왜,

BFS에서 노드 1 에서 다른 모든 노드 로 갈 때, 우리는 선착순 방식을 따릅니다. 예를 들어 노드 2 를 처리하기 전에 소스 에서 노드 3으로 갔습니다. 소스 에서 노드 3으로 이동하면 노드 4 를 5 + 3 = 8 로 업데이트 합니다 . 다시 노드 3 을 노드 2 에서 업데이트 할 때 노드 4 를 다시 3 + 3 = 6 으로 업데이트해야합니다! 따라서 노드 4 는 두 번 업데이트됩니다.

Dijkstra 는 First come, first serve 방법 대신에 가장 가까운 노드를 먼저 업데이트하면 업데이트가 적을 것이라고 제안했습니다. 이전에 노드 2 를 처리 한 경우 노드 3 은 이전에 업데이트되었을 것이며 노드 4를 적절히 업데이트 한 후에는 가장 짧은 거리를 쉽게 얻을 수 있습니다! 아이디어는 소스에 가장 가까운 노드 인 대기열에서 선택하는 것입니다. 그래서 여기에서 우선 순위 대기열 을 사용하여 대기열을 팝업 할 때 소스 에서 가장 가까운 노드 u 를 가져옵니다. 어떻게 그럴 수 있을까요? d [u] 의 값을 확인합니다.

의사 코드를 보자.

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

의사 코드는 소스 에서 다른 모든 노드의 거리를 반환합니다. 단일 노드 v의 거리를 알고 싶다면 v 가 대기열에서 팝되면 값을 반환 할 수 있습니다.

이제, Dijkstra의 알고리즘은 부정적인 가장자리가있을 때 작동합니까? 음수 사이클이 있으면 무한 루프가 발생하여 매번 비용이 계속 절감됩니다. 네거티브 엣지가 있더라도 Dijkstra는 목표가 터진 직후에 돌아 가지 않는 한 작동하지 않습니다. 그러나 Dijkstra 알고리즘은 아닙니다. 네거티브 엣지 / 사이클을 처리하기 위해 Bellman-Ford 알고리즘이 필요합니다.

복잡성:

BFS의 복잡도는 O (log (V + E)) 이며, 여기서 V 는 노드의 수이고 E 는 에지의 수입니다. Dijkstra의 경우 복잡성은 비슷하지만 Priority Queue의 정렬에는 O (logV)가 필요 합니다. 따라서 총 복잡도는 O (Vlog (V) + E)

다음은 Adjacency Matrix를 사용하여 Dijkstra의 최단 경로 알고리즘을 해결하는 Java 예제입니다.

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    void dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

프로그램의 예상 출력은 다음과 같습니다.

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14