예제가 포함된 DIJKSTRA의 최단 경로 알고리즘

다음 튜토리얼에서는 Dijkstra의 최단 경로 알고리즘에 대해 설명합니다. 단계별 그래픽 설명을 통해 Dijkstra 알고리즘의 작동을 이해합니다.

우리는 다음을 다룰 것입니다:

그래프의 기본 개념에 대한 간략한 개요
Dijkstra 알고리즘의 사용 이해
단계별 예제를 통해 알고리즘 작동 이해

이제 시작하겠습니다.

그래프에 대한 간략한 소개

그래프 요소 간의 '연결'을 나타내는 비선형 데이터 구조입니다. 이러한 요소는 다음과 같이 알려져 있습니다. 정점 , 그래프의 두 꼭지점을 연결하는 선이나 호를 가장자리 . 보다 공식적으로 그래프는 다음으로 구성됩니다. 정점 세트(V) 그리고 모서리 세트(E) . 그래프는 다음과 같이 표시됩니다. 지(V, E) .

그래프의 구성요소

정점:꼭짓점은 실제 사물, 사람 또는 엔터티를 나타내는 데 사용되는 그래프의 기본 단위입니다. 때로는 정점을 노드라고도 합니다.가장자리:모서리는 그래프의 두 꼭지점을 연결하는 데 그려지거나 사용됩니다. 때로는 가장자리를 호라고도 합니다.

다음 그림은 그래프의 그래픽 표현을 보여줍니다.

if else 문은 자바에서

그림 1: 그래프의 그래픽 표현

위 그림에서 Vertices/Node는 색칠된 원으로 표시되고 Edge는 노드를 연결하는 선으로 표시됩니다.

그래프의 응용

그래프는 실생활의 많은 문제를 해결하는 데 사용됩니다. 그래프는 네트워크를 나타내는 데 사용됩니다. 이러한 네트워크에는 전화, 회선 네트워크 또는 도시의 경로가 포함될 수 있습니다.

예를 들어 그래프를 사용하여 꼭지점은 제품을 보내거나 받는 시설을 표시하고 가장자리는 이를 연결하는 도로 또는 경로를 나타내는 운송 네트워크 모델을 설계할 수 있습니다. 다음은 동일한 내용을 그림으로 표현한 것입니다.

그림 2: 교통망의 그림 표현

그래프는 LinkedIn, Facebook, Twitter 등과 같은 다양한 소셜 미디어 플랫폼에서도 활용됩니다. 예를 들어, Facebook과 같은 플랫폼은 그래프를 사용하여 모든 사람이 정점으로 표시되는 사용자 데이터를 저장하며 각 그래프는 사람 ID, 이름, 성별, 주소 등과 같은 정보를 포함하는 구조입니다.

그래프 유형

그래프는 두 가지 유형으로 분류할 수 있습니다.

무방향 그래프
방향성 그래프

무방향 그래프: 방향이 없는 간선이 있는 그래프를 무방향 그래프라고 합니다. 이 그래프의 모서리는 각 모서리가 양방향으로 탐색될 수 있는 양방향 관계를 의미합니다. 다음 그림은 4개의 노드와 5개의 간선이 있는 간단한 무방향 그래프를 표시합니다.

그림 3: 간단한 무방향 그래프

방향성 그래프: 방향이 있는 간선이 있는 그래프를 방향 그래프라고 합니다. 이 그래프의 모서리는 각 모서리가 한 방향으로만 통과할 수 있는 단방향 관계를 의미합니다. 다음 그림은 4개의 노드와 5개의 간선이 있는 간단한 방향성 그래프를 표시합니다.

그림 4: 간단한 방향성 그래프

그래프 그림에서 모서리의 절대 길이, 위치 또는 방향은 특성상 의미가 없습니다. 즉, 그래프의 기본 구조가 변경되지 않으면 정점을 재배치하거나 가장자리를 왜곡하여 동일한 그래프를 다른 방식으로 시각화할 수 있습니다.

가중치 그래프란 무엇입니까?

그래프는 각 모서리에 '가중치'가 할당된 경우 가중치 그래프라고 합니다. 가장자리의 가중치는 거리, 시간 또는 가장자리가 연결하는 정점 쌍 사이의 '연결'을 모델링하는 모든 것을 나타낼 수 있습니다.

예를 들어, 다음 가중치 그래프 그림에서 각 모서리 옆에 파란색 숫자를 볼 수 있습니다. 이 숫자는 해당 모서리의 가중치를 나타내는 데 사용됩니다.

그림 5: 가중치 그래프의 예

Dijkstra 알고리즘 소개

이제 몇 가지 기본 그래프 개념을 알았으므로 Dijkstra 알고리즘의 개념을 이해해 보겠습니다.

Google 지도가 두 장소 사이의 가장 짧고 빠른 경로를 어떻게 찾는지 궁금한 적이 있나요?

글쎄, 대답은 Dijkstra의 알고리즘 . Dijkstra의 알고리즘 그래프 알고리즘입니다 최단 경로를 찾는 것입니다 소스 정점에서 그래프의 다른 모든 정점까지(단일 소스 최단 경로) 양의 가중치를 갖는 가중치 그래프에서만 작동하는 일종의 탐욕 알고리즘입니다. Dijkstra 알고리즘의 시간복잡도는 다음과 같습니다. 오(V²) 그래프의 인접 행렬 표현의 도움으로. 이 시간 복잡도는 다음과 같이 줄일 수 있습니다. O((V + E) 로그 V) 그래프의 인접 목록 표현을 사용하여 안에 정점의 개수이고 그리고 그래프의 간선 수입니다.

Dijkstra 알고리즘의 역사

Dijkstra의 알고리즘은 다음에 의해 설계되고 출판되었습니다. 박사. 에드저 W. 데이크스트라 , 네덜란드 컴퓨터 과학자, 소프트웨어 엔지니어, 프로그래머, 과학 수필가 및 시스템 과학자.

자바로 목록 정렬

2001년 ACM 저널의 Communications에 대한 Philip L. Frana와의 인터뷰에서 Edsger W. Dijkstra 박사는 다음과 같이 밝혔습니다.

'일반적으로 로테르담에서 흐로닝언까지 이동하는 가장 짧은 방법은 무엇입니까? 특정 도시에서 특정 도시로? 제가 약 20분만에 설계한 최단 경로 알고리즘입니다. 어느 날 아침, 어린 약혼자와 암스테르담에서 쇼핑을 하다가 피곤해서 카페 테라스에 앉아 커피 한 잔을 마시면서 내가 과연 이걸 할 수 있을까 고민하다가 최단 경로 알고리즘을 설계했습니다. . 내가 말했듯이, 그것은 20분짜리 발명품이었습니다. 사실 이 책은 3년 뒤인 59년에 출판됐다. 출판물은 여전히 읽을 수 있으며 실제로 매우 훌륭합니다. 너무 좋은 이유 중 하나는 연필과 종이를 사용하지 않고 디자인했기 때문입니다. 나는 연필과 종이 없이 디자인하는 것의 장점 중 하나가 피할 수 있는 모든 복잡성을 거의 피할 수 있다는 점을 나중에 알게 되었습니다. 결국 그 알고리즘은 놀랍게도 내 명성의 초석 중 하나가 되었습니다.'

Dijkstra는 1956년 암스테르담 수학 센터에서 프로그래머로 일하면서 ARMAC으로 알려진 새로운 컴퓨터의 기능을 설명하기 위해 최단 경로 문제에 대해 생각했습니다. 그의 목표는 컴퓨터에 대한 지식이 없는 사람들도 이해할 수 있는 문제와 해결책(컴퓨터에서 생성된)을 모두 선택하는 것이었습니다. 그는 최단 경로 알고리즘을 개발하고 나중에 ARMAC에서 네덜란드 64개 도시의 모호하게 단축된 교통 지도를 위해 이를 실행했습니다(64개 도시이므로 도시 번호를 인코딩하는 데 6비트이면 충분합니다). 1년 후, 그는 연구소의 다음 컴퓨터를 운영하는 하드웨어 엔지니어로부터 또 다른 문제를 발견했습니다. 기계 후면 패널의 핀을 연결하는 데 필요한 와이어의 양을 최소화하는 것입니다. 이에 대한 해결책으로 그는 프림의 최소 스패닝 트리 알고리즘이라는 알고리즘을 재발견하여 1959년에 발표했습니다.

Dijkstra 알고리즘의 기초

Dijkstra 알고리즘의 기본 개념은 다음과 같습니다.

Dijkstra의 알고리즘은 우리가 선택한 노드(소스 노드)에서 시작하여 그래프를 검사하여 해당 노드와 그래프의 다른 모든 노드 사이의 최단 경로를 찾습니다.
알고리즘은 각 노드에서 소스 노드까지 현재 확인된 최단 거리의 기록을 유지하고 더 짧은 경로를 찾으면 이 값을 업데이트합니다.
알고리즘이 소스와 다른 노드 사이의 최단 경로를 검색하면 해당 노드는 '방문'으로 표시되고 경로에 포함됩니다.
그래프의 모든 노드가 경로에 포함될 때까지 절차가 계속됩니다. 이러한 방식으로 소스 노드를 다른 모든 노드에 연결하는 경로가 생기며, 각 노드에 도달하는 최단 경로를 따릅니다.

Dijkstra 알고리즘의 작동 이해

ㅏ 그래프 그리고 소스 정점 Dijkstra 알고리즘의 요구 사항입니다. 이 알고리즘은 Greedy Approach를 기반으로 구축되었으므로 알고리즘의 각 단계에서 지역적으로 최적의 선택(이 경우 지역 최소값)을 찾습니다.

이 알고리즘의 각 정점에는 두 가지 속성이 정의되어 있습니다.

방문한 부동산
경로 속성

이러한 속성을 간략하게 이해해 보겠습니다.

방문한 부동산:

'visited' 속성은 해당 노드를 방문했는지 여부를 나타냅니다.
우리는 어떤 노드도 다시 방문하지 않도록 이 속성을 사용하고 있습니다.
최단 경로를 찾은 경우에만 노드를 방문한 것으로 표시됩니다.

경로 속성:

'path' 속성은 노드에 대한 현재 최소 경로 값을 저장합니다.
현재 최소 경로는 지금까지 이 노드에 도달한 가장 짧은 경로를 의미합니다.
이 속성은 노드의 이웃을 방문할 때 수정됩니다.
이 속성은 각 노드에 대한 최종 답변을 저장하므로 중요합니다.

처음에는 아직 방문하지 않은 모든 정점 또는 노드를 방문하지 않은 것으로 표시합니다. 모든 노드에 대한 경로도 소스 노드를 제외하고 무한대로 설정됩니다. 또한 소스 노드에 대한 경로는 0으로 설정됩니다.

그런 다음 소스 노드를 선택하고 방문한 것으로 표시합니다. 그 후 소스 노드의 모든 인접 노드에 액세스하고 모든 노드에서 완화를 수행합니다. 완화는 다른 노드의 도움을 받아 특정 노드에 도달하는 비용을 낮추는 프로세스입니다.

완화 과정에서 각 노드의 경로는 해당 노드의 현재 경로, 이전 노드까지의 경로, 이전 노드에서 현재 노드까지의 경로의 합 중 최소값으로 수정된다.

p[n]은 노드 n에 대한 현재 경로의 값, p[m]은 이전에 방문한 노드 m까지의 경로 값, w는 현재 노드와 노드 사이의 간선의 가중치라고 가정하자. 이전에 방문한 것(n과 m 사이의 간선 가중치).

수학적 의미에서 이완은 다음과 같이 예시될 수 있습니다.

p[n] = 최소(p[n], p[m] + w)

그런 다음 모든 후속 단계에서 방문하지 않은 노드를 최소 경로로 표시하고 이웃의 경로를 업데이트합니다.

그래프의 모든 노드가 방문한 것으로 표시될 때까지 이 절차를 반복합니다.

방문한 세트에 노드를 추가할 때마다 모든 인접 노드에 대한 경로도 그에 따라 변경됩니다.

: 자바에서

도달할 수 없는 노드(연결이 끊어진 구성 요소)가 있는 경우 해당 경로는 '무한대'로 유지됩니다. 소스 자체가 별도의 구성요소인 경우 다른 모든 노드에 대한 경로는 '무한대'로 유지됩니다.

예제를 통해 Dijkstra 알고리즘 이해하기

다음은 Dijkstra 알고리즘을 구현하기 위해 따라야 할 단계입니다.

1 단계: 먼저 소스 노드를 현재 거리 0으로 표시하고 나머지 노드를 INFINITY로 설정합니다.

2 단계: 그런 다음 현재 거리가 가장 작은 방문하지 않은 노드를 현재 노드(X라고 가정)로 설정합니다.

3단계: 현재 노드 X의 각 이웃 N에 대해: 그런 다음 X의 현재 거리에 X-N을 연결하는 가장자리의 가중치를 추가합니다. 현재 N의 거리보다 작다면 새로운 현재 거리 N으로 설정합니다.

4단계: 그런 다음 현재 노드 X를 방문한 것으로 표시합니다.

5단계: 우리는 다음부터 과정을 반복할 것입니다. '2 단계' 그래프에 방문하지 않은 노드가 남아 있는 경우.

이제 예제를 통해 알고리즘 구현을 이해해 보겠습니다.

그림 6: 주어진 그래프

위의 그래프를 노드와 함께 입력으로 사용합니다. ㅏ 소스로.
먼저 모든 노드를 방문하지 않은 노드로 표시합니다.
우리는 경로를 다음과 같이 설정할 것입니다. 0 노드에서 ㅏ 그리고 무한대 다른 모든 노드에 대해.
이제 소스 노드를 표시하겠습니다. ㅏ 방문한 대로 이웃 노드에 액세스합니다.
메모: 우리는 이웃 노드에만 접근했고, 방문하지는 않았습니다.
이제 노드 경로를 업데이트하겠습니다. 비 ~에 의해 4 노드에 대한 경로 때문에 휴식의 도움으로 ㅏ ~이다 0 그리고 노드로부터의 경로 ㅏ 에게 비 ~이다 4 , 그리고 최소((0 + 4), 무한대) ~이다 4 .
또한 노드 경로도 업데이트하겠습니다. 씨 ~에 의해 5 노드에 대한 경로 때문에 휴식의 도움으로 ㅏ ~이다 0 그리고 노드로부터의 경로 ㅏ 에게 씨 ~이다 5 , 그리고 최소((0 + 5), 무한대) ~이다 5 . 노드의 이웃 모두 ㅏ 이제 편안해졌습니다. 그러므로 우리는 앞으로 나아갈 수 있습니다.
이제 경로가 가장 적은 다음 방문하지 않은 노드를 선택하여 방문하겠습니다. 따라서 노드를 방문하겠습니다. 비 방문하지 않은 이웃에게 휴식을 제공합니다. 이완을 수행한 후 노드까지의 경로 씨 남을 것이다 5 , 노드에 대한 경로 그리고 될 것입니다 열하나 및 노드 경로 디 될 것입니다 13 .
이제 노드를 방문하겠습니다. 그리고 이웃 노드에 대해 이완을 수행합니다. 비, 디 , 그리고 에프 . 노드만 있기 때문에 에프 방문하지 않으면 편안해질 것입니다. 따라서 노드에 대한 경로는 비 그대로 유지됩니다. 즉, 4 , 노드의 경로 디 도 남을 것이다 13 및 노드 경로 에프 될 것입니다 14 (8 + 6) .
이제 노드를 방문하겠습니다. 디 및 노드만 에프 편안해질 것입니다. 그러나 노드에 대한 경로는 에프 변경되지 않은 상태로 유지됩니다. 즉, 14 .
노드만 있기 때문에 에프 남아 있는 경우, 우리는 그것을 방문할 것이지만 모든 이웃 노드가 이미 방문되었으므로 어떠한 완화도 수행하지 않을 것입니다.
그래프의 모든 노드를 방문하면 프로그램이 종료됩니다.

따라서 우리가 내린 최종 경로는 다음과 같습니다.

 A = 0 B = 4 (A -&gt; B) C = 5 (A -&gt; C) D = 4 + 9 = 13 (A -&gt; B -&gt; D) E = 5 + 3 = 8 (A -&gt; C -&gt; E) F = 5 + 3 + 6 = 14 (A -&gt; C -&gt; E -&gt; F)

Dijkstra 알고리즘의 의사 코드

이제 우리는 Dijkstra 알고리즘의 의사코드를 이해하겠습니다.

우리는 모든 노드의 경로 거리에 대한 기록을 유지해야 합니다. 따라서 각 노드의 경로 거리를 n 크기의 배열에 저장할 수 있습니다. 여기서 n은 총 노드 수입니다.
또한, 우리는 해당 경로의 길이와 함께 최단 경로를 검색하려고 합니다. 이 문제를 극복하기 위해 각 노드를 경로 길이를 마지막으로 업데이트한 노드에 매핑합니다.
알고리즘이 완료되면 대상 노드를 소스 노드로 역추적하여 경로를 검색할 수 있습니다.
최소 우선순위 큐를 사용하여 효율적인 방법으로 경로 거리가 가장 짧은 노드를 검색할 수 있습니다.

이제 위 그림의 의사코드를 구현해 보겠습니다.

유사 코드:

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

설명:

위의 코드 조각에는 다음이 포함되었습니다. stdio.h 헤더 파일은 두 개의 상수 값을 정의했습니다. INF = 9999 그리고 최대 = 10 . 우리는 함수의 프로토타입을 선언한 다음 Dijkstra 알고리즘에 대한 함수를 다음과 같이 정의했습니다. Dijkstra알고리즘 이는 노드로 구성된 그래프, 그래프의 노드 수 및 소스 노드의 세 가지 인수를 허용합니다. 이 함수 내에서 우리는 알고리즘의 우선순위 큐로 작동할 2D 매트릭스, 노드 사이의 거리를 유지하는 배열, 이전 노드의 기록을 유지하는 배열, 저장할 배열과 같은 일부 데이터 구조를 정의했습니다. 방문한 노드 정보 및 최소 거리 값, 카운터, 다음 노드 값 등을 저장하는 일부 정수 변수. 그런 다음 우리는 중첩된 for 루프 그래프의 노드를 반복하고 이에 따라 우선 순위 대기열에 추가합니다. 우리는 다시 for 루프 소스 노드부터 시작하여 우선순위 큐의 요소를 반복하고 거리를 업데이트합니다. 루프 외부에서는 소스 노드의 거리를 다음과 같이 설정했습니다. 0 그리고 그것을 방문한 것으로 표시했습니다. Visited_nodes[] 정렬. 그런 다음 카운터 값을 1로 설정하고 ~하는 동안 노드 수를 반복하는 루프입니다. 이 루프 내에서 우리는 다음의 값을 설정했습니다. 최소_거리 ~처럼 INF 그리고는 for 루프 값을 업데이트하려면 최소_거리 a의 최소값을 갖는 변수 거리[] 정렬. 그런 다음 다음을 사용하여 선택한 노드의 방문하지 않은 이웃 노드를 반복했습니다. for 루프 그리고 휴식을 취했습니다. 그런 다음 Dijkstra 알고리즘을 사용하여 계산된 거리의 결과 데이터를 인쇄했습니다.

에서 기본 함수에서는 그래프를 나타내는 변수와 노드 수, 소스 노드를 정의하고 선언했습니다. 마침내 우리는 전화를 걸었습니다. 다익스트라알고리즘() 필수 매개변수를 전달하여 기능을 수행합니다.

결과적으로 소스 노드의 모든 노드에 대해 필요한 최단 경로가 사용자에게 인쇄됩니다.

C++의 Dijkstra 알고리즘 코드

다음은 C++ 프로그래밍 언어로 Dijkstra 알고리즘을 구현한 것입니다.

파일: DijkstraAlgorithm.cpp

첫 번째 문자 제거 엑셀

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

설명:

위의 코드 조각에는 다음이 포함되었습니다. '아이오스트림' 그리고 '벡터' 헤더 파일을 작성하고 상수 값을 다음과 같이 정의했습니다. MAX_INT = 10000000 . 그런 다음 표준 네임스페이스를 사용하여 프로토타입을 만들었습니다. 다익스트라알고리즘() 기능. 그런 다음 우리는 프로그램의 주요 기능을 정의했습니다. 다익스트라알고리즘() 기능. 그 후 정점과 가장자리를 생성하기 위한 일부 클래스를 선언했습니다. 또한 소스 정점에서 대상 정점까지 가능한 최단 경로를 찾기 위해 더 많은 함수의 프로토타입을 만들고 Vertex 및 Edge 클래스를 인스턴스화했습니다. 그런 다음 그래프의 정점과 가장자리를 생성하기 위해 두 클래스를 모두 정의했습니다. 그런 다음 우리는 다익스트라알고리즘() 그래프를 생성하고 다양한 작업을 수행하는 기능입니다. 이 함수 내에서 일부 정점과 가장자리를 선언했습니다. 그런 다음 그래프의 소스 정점을 설정하고 데이크스트라() 가장 짧은 거리를 찾는 함수와 Print_Shortest_Route_To() 소스 정점에서 정점까지의 최단 거리를 인쇄하는 함수 '에프' . 그런 다음 우리는 데이크스트라() 소스 정점으로부터 모든 정점의 가능한 최단 거리를 계산하는 함수입니다. 또한 가장 짧은 거리를 가진 정점을 찾아 나머지 정점에 인접한 모든 정점을 반환하고, 연결된 두 정점 사이의 거리를 반환하고, 선택한 정점이 그래프에 존재하는지 확인하고, 소스 정점에서 대상 정점까지의 가능한 최단 경로입니다.

결과적으로 정점에 필요한 최단 경로는 '에프' 소스 노드의 내용이 사용자에게 인쇄됩니다.

Java의 Dijkstra 알고리즘 코드

다음은 Java 프로그래밍 언어로 Dijkstra 알고리즘을 구현한 것입니다.

파일: DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

설명:

위의 코드 조각에서 우리는 공개 클래스를 다음과 같이 정의했습니다. 다익스트라알고리즘() . 이 클래스 내에서 우리는 공개 메소드를 다음과 같이 정의했습니다. 다익스트라알고리즘() 원본 정점에서 대상 정점까지의 최단 거리를 찾습니다. 이 메서드 내에서 노드 수를 저장하는 변수를 정의했습니다. 그런 다음 방문한 정점에 관한 정보를 저장하는 부울 배열과 각각의 거리를 저장하는 정수 배열을 정의했습니다. 처음에는 두 배열의 값을 다음과 같이 선언했습니다. 거짓 그리고 MAX_VALUE , 각각. 또한 소스 정점의 거리를 0으로 설정하고 for 루프 소스 정점과 대상 정점 사이의 거리를 최소 거리로 업데이트합니다. 그런 다음 완화를 수행하여 선택한 정점의 인접 정점의 거리를 업데이트하고 모든 정점에 대해 최단 거리를 인쇄했습니다. 그런 다음 소스 정점에서 대상 정점까지의 최소 거리를 찾는 방법을 정의했습니다. 그런 다음 그래프의 정점을 선언하고 인스턴스화하는 기본 함수를 정의했습니다. 다익스트라알고리즘() 수업. 마지막으로 우리는 다익스트라알고리즘() 소스 정점과 대상 정점 사이의 최단 거리를 찾는 방법.

결과적으로 소스 노드의 모든 노드에 대해 필요한 최단 경로가 사용자에게 인쇄됩니다.

지금 자바 날짜

Python의 Dijkstra 알고리즘 코드

다음은 Python 프로그래밍 언어로 Dijkstra 알고리즘을 구현한 것입니다.

파일: DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

산출

 Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3

설명:

위의 코드 조각에서 우리는 시스템 모듈을 만들고 노드와 에지의 값으로 구성된 목록을 선언했습니다. 그런 다음 함수를 다음과 같이 정의했습니다. 방문 예정() 다음에 방문할 노드를 찾으려면 그런 다음 그래프에서 총 노드 수를 찾고 모든 노드의 초기 거리를 설정했습니다. 그런 다음 소스 노드에서 대상 노드까지의 최소 거리를 계산하고, 이웃 노드에 대해 완화를 수행하고, 목록의 거리를 업데이트했습니다. 그런 다음 사용자를 위해 목록에서 해당 거리를 인쇄했습니다.

결과적으로 소스 노드의 모든 노드에 대해 필요한 최단 경로가 사용자에게 인쇄됩니다.

Dijkstra 알고리즘의 시간 및 공간 복잡성

Dijkstra 알고리즘의 시간 복잡도는 다음과 같습니다. O(E로그V) 여기서 E는 모서리 수이고 V는 정점 수입니다.
Dijkstra 알고리즘의 공간 복잡도는 O(V)이며, 여기서 V는 정점의 수입니다.

Dijkstra 알고리즘의 장점과 단점

Dijkstra 알고리즘의 몇 가지 장점에 대해 논의해 보겠습니다.

Dijkstra 알고리즘을 사용하는 주요 이점 중 하나는 거의 선형적인 시간 및 공간 복잡성을 갖는다는 것입니다.
이 알고리즘을 사용하면 대상 정점에 대한 최단 거리를 얻은 후 알고리즘을 중지하여 단일 정점에서 다른 모든 정점까지의 최단 경로와 단일 소스 정점에서 단일 대상 정점까지의 최단 경로를 계산할 수 있습니다.
이 알고리즘은 방향성 가중치 그래프에만 작동하며 이 그래프의 모든 가장자리는 음수가 아니어야 합니다.

여러 가지 장점에도 불구하고 Dijkstra 알고리즘에는 다음과 같은 몇 가지 단점도 있습니다.

Dijkstra 알고리즘은 그 과정에서 많은 시간을 활용하는 은폐 탐색을 수행합니다.
이 알고리즘은 음의 가장자리를 처리하는 데에는 효과가 없습니다.
이 알고리즘은 비순환 그래프로 향하기 때문에 정확한 최단 경로를 계산할 수 없습니다.
또한 방문한 정점에 대한 기록을 유지하려면 유지 관리가 필요합니다.

Dijkstra 알고리즘의 일부 응용

Dijkstra의 알고리즘에는 다양한 실제 응용 프로그램이 있으며 그 중 일부는 아래에 설명되어 있습니다.

Google 지도의 디지털 지도 서비스:Google 지도에서 우리 위치에서 가장 가까운 선호 위치까지 또는 한 도시에서 다른 도시까지의 거리를 찾으려고 여러 번 시도했는데, 이는 여러 경로/경로를 연결하는 경로로 구성됩니다. 그러나 애플리케이션은 최소 거리를 표시해야 합니다. 이는 Dijkstra의 알고리즘이 응용 프로그램이 경로를 따라 주어진 두 위치 사이에서 가장 짧은 위치를 찾는 데 도움이 되기 때문에 가능합니다. 도시/장소를 정점으로 표현하고, 두 도시/장소 사이의 경로를 모서리로 표현한 그래프로 미국을 생각해 보겠습니다. 그런 다음 Dijkstra 알고리즘의 도움으로 두 도시/장소 사이의 최단 경로를 계산할 수 있습니다.소셜 네트워킹 애플리케이션:Facebook, Twitter, Instagram 등과 같은 많은 애플리케이션에서 우리 중 많은 사람들은 이러한 앱이 특정 사용자가 알 수 있는 친구 목록을 제안하는 것을 관찰했을 것입니다. 많은 소셜 미디어 회사는 특히 시스템 사용자가 10억 명이 넘는 경우 이러한 유형의 기능을 어떻게 효율적이고 효과적인 방식으로 구현합니까? 이 질문에 대한 답은 다익스트라 알고리즘(Dijkstra's Algorithm)입니다. 표준 Dijkstra 알고리즘은 일반적으로 사용자 간의 연결이나 상호성을 통해 측정된 사용자 간의 최단 거리를 추정하는 데 사용됩니다. 소셜 네트워킹의 규모가 아주 작은 경우에는 최단 경로를 결정하기 위해 표준 Dijkstra 알고리즘과 기타 기능을 사용합니다. 그러나 그래프가 훨씬 커지면 표준 알고리즘을 사용하여 계산하는 데 몇 초가 걸리므로 일부 고급 알고리즘이 대안으로 사용됩니다.전화 네트워크:우리 중 일부는 알고 있듯이 전화 네트워크에서 각 전송 회선에는 대역폭 'b'가 있습니다. 대역폭은 전송선이 지원할 수 있는 가장 높은 주파수입니다. 일반적으로 특정 라인에서 신호의 주파수가 더 높으면 해당 라인만큼 신호가 감소합니다. 대역폭은 회선을 통해 전송할 수 있는 정보의 양을 나타냅니다. 스위칭 스테이션을 정점으로 표현하고, 전송선을 에지로 표현하고, 대역폭 'b'를 에지의 가중치로 표현하는 그래프로 도시를 생각해 보자. 따라서 우리가 볼 수 있듯이 전화망도 최단 거리 문제의 범주에 속할 수 있으며 Dijkstra 알고리즘을 사용하여 해결할 수 있습니다.비행 프로그램:고객을 위한 항공편 일정을 준비하기 위해 소프트웨어가 필요하다고 가정해 보겠습니다. 에이전트는 모든 항공편과 공항이 포함된 데이터베이스에 액세스할 수 있습니다. 항공편 번호, 출발 공항, 목적지 외에도 항공편에는 출발 및 도착 시간도 있습니다. 따라서 원래 공항에서 선택한 목적지의 가장 빠른 도착 시간과 주어진 시작 시간을 결정하기 위해 에이전트는 Dijkstra 알고리즘을 사용합니다.개방형 최단 경로를 먼저 찾기 위한 IP 라우팅:Open Shortest Path First(OSPF로 약칭)는 자체 Shortest Path First를 사용하여 소스 라우터와 대상 라우터 사이의 최상의 경로를 찾는 데 사용되는 링크 상태 라우팅 프로토콜입니다. Dijkstra의 알고리즘은 포워딩 테이블을 업데이트하기 위해 라우터에 필요한 라우팅 프로토콜에 광범위하게 활용됩니다. 이 알고리즘은 소스 라우터에서 네트워크에 있는 다른 라우터까지의 최단 비용 경로를 제공합니다.로봇 경로:요즘에는 드론과 로봇이 등장했는데, 일부는 수동으로 작동하고 일부는 자동으로 작동합니다. 자동으로 작동되어 특정 위치로 패키지를 배달하거나 특정 작업에 사용되는 드론과 로봇은 Dijkstra의 알고리즘 모듈로 구성되어 소스와 목적지가 알려지면 드론과 로봇이 명령된 방향으로 이동합니다. 패키지를 배송하기 위해 소요되는 시간을 최소화하면서 최단 경로를 따라갑니다.파일 서버를 지정합니다:Dijkstra 알고리즘은 LAN(Local Area Network)에서 파일 서버를 지정하는 데에도 사용됩니다. 한 컴퓨터에서 다른 컴퓨터로 파일을 전송하는 데 무한한 시간이 필요하다고 가정해 보겠습니다. 따라서 파일 서버에서 네트워크의 다른 모든 컴퓨터로의 '홉' 수를 최소화하기 위해 Dijkstra 알고리즘을 사용합니다. 이 알고리즘은 네트워크 간의 최단 경로를 반환하여 최소 홉 수를 생성합니다.

결론

위의 튜토리얼에서는 먼저 Graph의 기본 개념과 유형 및 응용 프로그램을 이해했습니다.
그런 다음 Dijkstra 알고리즘과 그 역사에 대해 배웠습니다.
우리는 또한 예제의 도움을 받아 Dijkstra 알고리즘의 기본 작동을 이해했습니다.
그 후, 의사코드(Pseudocode)의 도움을 받아 다익스트라 알고리즘(Dijkstra's Algorithm)에 대한 코드를 작성하는 방법을 연구했습니다.
적절한 출력과 설명을 통해 C, C++, Java 및 Python과 같은 프로그래밍 언어로 구현되는 것을 관찰했습니다.
우리는 또한 Dijkstra 알고리즘의 시간과 공간 복잡성을 이해했습니다.
마지막으로 Dijkstra 알고리즘과 실제 응용 프로그램의 장점과 단점에 대해 논의했습니다.