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