how implement dijkstra s algorithm java
이 자습서에서는 예제를 사용하여 그래프 또는 트리에서 최단 경로를 찾기 위해 Java에서 Dijkstra의 알고리즘을 구현하는 방법을 설명합니다.
Java의 Graphs에 대한 이전 자습서에서 그래프를 사용하여 다른 응용 프로그램과는 별도로 노드 간의 최단 경로를 찾는 것을 확인했습니다.
그래프의 두 노드 사이의 최단 경로를 찾기 위해 우리는 주로 ' Dijkstra의 알고리즘 ”. 이 알고리즘은 그래프 나 트리에서 최단 경로를 찾는 데 널리 사용되는 알고리즘입니다.
학습 내용 :
Dijkstra의 자바 알고리즘
가중치가 적용된 그래프와 그래프의 시작 (소스) 꼭지점이 주어지면 Dijkstra의 알고리즘을 사용하여 소스 노드에서 그래프의 다른 모든 노드까지의 최단 거리를 찾습니다.
그래프에서 Dijkstra의 알고리즘을 실행 한 결과 소스 정점이 루트 인 최단 경로 트리 (SPT)를 얻습니다.
Dijkstra의 알고리즘에서는 두 세트 또는 목록을 유지합니다. 하나는 최단 경로 트리 (SPT)의 일부인 정점을 포함하고 다른 하나는 SPT에 포함되도록 평가되는 정점을 포함합니다. 따라서 모든 반복에 대해 가장 짧은 경로를 가진 두 번째 목록에서 정점을 찾습니다.
Dijkstra의 최단 경로 알고리즘에 대한 의사 코드는 다음과 같습니다.
데이터 수집 도구 란?
의사 코드
다음은이 알고리즘의 의사 코드입니다.
procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end 이제 샘플 그래프를 사용하여 Dijkstra의 최단 경로 알고리즘을 설명하겠습니다. .
처음에는 SPT (Shortest Path Tree) 세트가 무한대로 설정됩니다.
정점 0부터 시작하겠습니다. 먼저 정점 0을 sptSet에 넣습니다.
sptSet = {0, INF, INF, INF, INF, INF}.
다음으로 sptSet의 정점 0을 사용하여 인접 항목을 탐색합니다. 정점 1과 2는 각각 거리가 2와 1 인 0의 인접한 두 노드입니다.
위의 그림에서 우리는 또한 소스 정점 0으로부터의 각각의 거리로 인접한 각 정점 (1과 2)을 업데이트했습니다. 이제 정점 2가 최소 거리를 가지고 있음을 알 수 있습니다. 다음으로 정점 2를 sptSet에 추가합니다. 또한 정점 2의 이웃을 탐색합니다.
이제 우리는 최소 거리를 가진 정점과 spt에없는 정점을 찾습니다. 거리 2로 정점 1을 선택합니다.
위 그림에서 볼 수 있듯이 2, 0, 1의 모든 인접 노드 중 이미 sptSet에 있으므로 무시합니다. 인접한 노드 5와 3 중 5는 비용이 가장 적습니다. 그래서 우리는 그것을 sptSet에 추가하고 인접한 노드를 탐색합니다.
위의 그림에서 노드 3과 4를 제외하고 다른 모든 노드는 sptSet에 있습니다. 3과 4 중 노드 3은 비용이 가장 적습니다. 그래서 우리는 그것을 sptSet에 넣었습니다.
위와 같이 이제 4 개의 버텍스 만 남았고 루트 노드로부터의 거리는 16입니다. 마지막으로 sptSet에 넣어 최종 sptSet = {0, 2, 1, 5, 3, 4}를 얻습니다. 소스 노드 0에서 각 정점의 거리를 제공합니다.
Java에서 Dijkstra의 알고리즘 구현
Java에서 Dijkstra의 최단 경로 알고리즘을 구현하는 방법은 두 가지입니다. 우선 순위 대기열과 인접 목록을 사용하거나 인접 행렬과 배열을 사용할 수 있습니다.
이 섹션에서는 두 가지 구현을 모두 볼 수 있습니다.
우선 순위 대기열 사용
이 구현에서는 우선 순위 대기열을 사용하여 최단 거리의 정점을 저장합니다. 그래프는 인접 목록을 사용하여 정의됩니다. 샘플 프로그램은 아래와 같습니다.
import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i 산출:
인접 행렬 사용
이 접근 방식에서는 인접 행렬을 사용하여 그래프를 나타냅니다. spt 세트의 경우 배열을 사용합니다.
다음 프로그램은이 구현을 보여줍니다.
import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v 산출:
자주 묻는 질문
Q # 1) Dijkstra는 무 방향 그래프에서 작동합니까?
대답: 그래프가 방향성인지 무 방향성인지는 Dijkstra의 알고리즘의 경우 중요하지 않습니다. 이 알고리즘은 그래프의 정점과 가중치에만 관련됩니다.
Q # 2) Dijkstra 알고리즘의 시간 복잡도는 무엇입니까?
대답: Dijkstra 알고리즘의 시간 복잡도는 O입니다 (V 2). 최소 우선 순위 대기열로 구현할 때이 알고리즘의 시간 복잡도는 O (V + E l o g V)로 떨어집니다.
Q # 3) Dijkstra는 탐욕스러운 알고리즘입니까?
대답: 예, Dijkstra는 탐욕스러운 알고리즘입니다. 최소 스패닝 트리 (MST)를 찾는 Prim의 알고리즘과 유사하게 이러한 알고리즘은 루트 정점에서 시작하며 항상 최소 경로로 가장 최적의 정점을 선택합니다.
Q # 4) Dijkstra DFS 또는 BFS입니까?
대답: 둘 다 아닙니다. 그러나 Dijkstra의 알고리즘은 구현을 위해 우선 순위 대기열을 사용하므로 BFS에 가까운 것으로 볼 수 있습니다.
Q # 5) Dijkstra 알고리즘은 어디에 사용됩니까?
대답: 한 노드에서 다른 노드로의 최단 경로를 찾는 데 도움이되므로 라우팅 프로토콜에서 주로 사용됩니다.
결론
이 튜토리얼에서는 Dijkstra의 알고리즘에 대해 논의했습니다. 이 알고리즘을 사용하여 루트 노드에서 그래프 또는 트리의 다른 노드까지의 최단 경로를 찾습니다.
최소 경로를 찾아야하므로 일반적으로 우선 순위 대기열을 사용하여 Dijkstra의 알고리즘을 구현합니다. 인접 행렬을 사용하여이 알고리즘을 구현할 수도 있습니다. 이 튜토리얼에서이 두 가지 접근 방식에 대해 논의했습니다.
이 튜토리얼이 도움이되기를 바랍니다.
=> 모두를위한 Java 교육 시리즈를 보려면 여기를 방문하십시오.
추천 도서
