분류 javascript

Dijkstra의 최단 경로 알고리즘-상세하고 시각적인 소개

컨텐츠 정보

  • 조회 337 (작성일 )

본문

어서 오십시오! 항상 Dijkstra의 알고리즘을 배우고 이해하고 싶었다면 이 기사가 적합합니다. 단계별 그래픽 설명을 통해 무대 뒤에서 어떻게 작동하는지 확인할 수 있습니다.


https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/


당신은 배울 것이다:


  • 기본 그래프 개념 (간단한 검토).
  • Dijkstra의 알고리즘이 사용되는 것.
  • 단계별 예제를 통해 무대 뒤에서 어떻게 작동하는지.


? 그래프 소개 


그래프에 대한 간략한 소개부터 시작하겠습니다.


기본 개념 


그래프는 요소 쌍 간의 "연결"을 나타내는 데 사용되는 데이터 구조입니다.


  • 이러한 요소를 노드라고 합니다. 실제 개체, 사람 또는 개체를 나타냅니다.
  • 노드 간의 연결을 가장자리라고 합니다.

다음은 그래프의 그래픽 표현입니다.


image-123.png 

노드는 색상이 있는 원으로 표시되고 가장자리는 이러한 원을 연결하는 선으로 표시됩니다.


? 팁 : 두 노드 사이에 가장자리가 있으면 두 노드가 연결됩니다.


Applications 


그래프는 실제 시나리오에 직접 적용 할 수 있습니다. 예를 들어 그래프를 사용하여 노드가 제품을 보내거나 받는 시설을 나타내고 가장자리가 이를 연결하는 도로 또는 경로를 나타내는 교통 네트워크를 모델링 할 수 있습니다 (아래 참조).


image-121.png 


Types of Graphs 


그래프는 다음과 같습니다.


  • Undirected : 연결된 모든 노드 쌍에 대해 한 노드에서 다른 노드로 양방향으로 이동할 수 있습니다.
  • Directed : 연결된 모든 노드 쌍에 대해 특정 방향으로 한 노드에서 다른 노드로만 이동할 수 있습니다. 단순한 선 대신 화살표를 사용하여 방향이 있는 가장자리를 나타냅니다.

image-124.png 


? 팁 :이 기사에서는 무 방향 그래프로 작업 할 것입니다.


Weighted Graphs 


가중치 그래프는 가장자리에 "가중치"또는 "비용"이 있는 그래프입니다. 에지의 가중치는 거리, 시간 또는 연결하는 노드 쌍 간의 "연결"을 모델링 하는 모든 것을 나타낼 수 있습니다.


예를 들어 아래 가중치 그래프에서 각 모서리 옆에 파란색 숫자가 표시됩니다. 이 숫자는 해당 모서리의 가중치를 나타내는 데 사용됩니다.


image-126.png 

? 팁 :이 가중치는 Dijkstra의 알고리즘에 필수적입니다. 그 이유는 잠시 후에 알게 될 것입니다.


? Dijkstra의 알고리즘 소개 


이제 그래프의 기본 개념을 알았으므로 이 놀라운 알고리즘을 살펴 보겠습니다.


  • 목적 및 사용 사례
  • 역사
  • 알고리즘의 기초
  • 요구 사항

목적 및 사용 사례 


Dijkstra의 알고리즘을 사용하면 그래프에서 노드 간의 최단 경로를 찾을 수 있습니다. 특히 노드 ( "소스 노드"라고 함)에서 그래프의 다른 모든 노드로의 최단 경로를 찾아 최단 경로 트리를 생성 할 수 있습니다.


이 알고리즘은 GPS 장치에서 현재 위치와 목적지 사이의 최단 경로를 찾는 데 사용됩니다. 업계, 특히 모델링 네트워크가 필요한 도메인에서 광범위한 응용 프로그램을 가지고 있습니다.


역사 


이 알고리즘은 뛰어난 네덜란드 컴퓨터 과학자이자 소프트웨어 엔지니어 인 Edsger W. Dijkstra 박사가 만들고 게시했습니다.


1959 년에 그는 "그래프와 관련된 두 가지 문제에 대한 노트"라는 제목의 3 페이지 짜리 기사를 발표하여 새로운 알고리즘을 설명했습니다.


image-112.png 


2001 년 인터뷰에서 Dr. Dijkstra는 그가 알고리즘을 설계 한 방법과 이유를 밝혔습니다.


로테르담에서 흐로 닝언까지 이동하는 가장 짧은 방법은 무엇입니까? 약 20 분 만에 설계 한 최단 경로 알고리즘입니다. 어느 날 아침 나는 젊은 약혼자와 암스테르담에서 쇼핑을 하다가 피곤해서 카페 테라스에 앉아 커피 한 잔을 마실 수 있을지 생각하고 있었다. 그리고 나서 최단 경로 알고리즘을 설계했다. . 제가 말했듯이 그것은 20 분의 발명이었습니다. 사실이 책은 3 년 후인 1959 년에 출판되었습니다. 출판물은 여전히 ​​아주 훌륭합니다. 이렇게 좋은 이유 중 하나는 연필과 종이 없이 디자인했기 때문입니다. 연필과 종이가 없으면 피할 수 있는 모든 복잡성을 피해야 합니다. 결국 그 알고리즘은 놀랍게도 제 명성의 초석 중 하나가 되었습니다. — Edsger W. Dijkstra와의 인터뷰에서 Edsger W. Dijkstra 기사에서 인용 한대로. 


⭐ 믿기지 않죠? 20 분 만에 Dijkstra 박사는 컴퓨터 과학 역사상 가장 유명한 알고리즘 중 하나를 설계했습니다.


Dijkstra 알고리즘의 기초 

  • Dijkstra의 알고리즘은 기본적으로 선택한 노드 (소스 노드)에서 시작하고 그래프를 분석하여 해당 노드와 그래프의 다른 모든 노드 사이의 최단 경로를 찾습니다.
  • 알고리즘은 각 노드에서 소스 노드까지 현재 알려진 최단 거리를 추적하고 더 짧은 경로를 찾으면 이 값을 업데이트합니다.
  • 알고리즘이 소스 노드와 다른 노드 사이의 최단 경로를 찾으면 해당 노드는 "방문 됨"으로 표시되고 경로에 추가됩니다.
  • 그래프의 모든 노드가 경로에 추가 될 때까지 프로세스가 계속됩니다. 이렇게 하면 소스 노드를 각 노드에 도달 할 수 있는 최단 경로를 따라 다른 모든 노드에 연결하는 경로가 있습니다.


요구 사항 


Dijkstra의 알고리즘은 양의 가중치를 가진 그래프에서만 작동합니다. 이는 프로세스 중에 최단 경로를 찾기 위해 가장자리의 가중치를 추가해야 하기 때문입니다.


그래프에 음의 가중치가 있으면 알고리즘이 제대로 작동하지 않습니다. 노드가 "방문 됨"으로 표시되면 해당 노드에 대한 현재 경로가 해당 노드에 도달하기 위한 최단 경로로 표시됩니다. 이 단계가 발생한 후 총 가중치가 감소 할 수 있는 경우 음의 가중치가 이를 변경할 수 있습니다.


? 예 


이제 이 알고리즘에 대해 더 많이 알게 되었으므로 단계별 예제를 통해 백그라운드에서 어떻게 작동하는지 살펴 보겠습니다.


이 그래프가 있습니다.


image-76.png 


알고리즘은 노드 0에서 그래프의 다른 모든 노드까지의 최단 경로를 생성합니다.


? 팁 :이 그래프에서는 가장자리의 가중치가 두 노드 사이의 거리를 나타낸다고 가정합니다.


그래프의 모든 노드에 대해 노드 0에서 노드 1로, 노드 0에서 노드 2로, 노드 0에서 노드 3으로의 최단 경로를 갖게 됩니다.


처음에는 다음과 같은 거리 목록이 있습니다 (아래 목록 참조).


  • 소스 노드에서 자체까지의 거리는 0입니다.이 예에서 소스 노드는 노드 0이되지만 선택한 노드가 될 수 있습니다.
  • 소스 노드에서 다른 모든 노드까지의 거리는 아직 결정되지 않았으므로 처음에는 무한대 기호를 사용하여 이를 나타냅니다.

image-77.png 


또한 아직 방문하지 않은 노드 (경로에 포함되지 않은 노드)를 추적하기 위해 이 목록 (아래 참조)이 있습니다.


image-78.png 

? 팁 : 모든 노드가 경로에 추가되면 알고리즘이 완료됩니다.


노드 0에서 시작하도록 선택 했으므로 이 노드를 방문한 것으로 표시 할 수 있습니다. 마찬가지로, 방문하지 않은 노드 목록에서 제거하고 다이어그램의 해당 노드에 빨간색 테두리를 추가합니다.


image-87.png 


image-83.png 

이제 노드 0에서 인접 노드까지의 거리를 확인해야 합니다. 보시다시피 노드 1과 2는 다음과 같습니다 (빨간색 가장자리 참조).


image-89.png 


? 팁 : 이것은 우리가 가장 짧은 경로에 두 개의 인접한 노드를 즉시 추가한다는 것을 의미하지는 않습니다. 이 경로에 노드를 추가하기 전에 가장 짧은 경로를 찾았는지 확인해야 합니다. 우리는 사용 가능한 옵션을 보기 위해 초기 검사 프로세스를 만드는 것입니다.


노드 0 (소스 노드)에 연결하는 가장자리의 가중치로 노드 0에서 노드 1 및 노드 2까지의 거리를 업데이트 해야 합니다. 이러한 가중치는 각각 2와 6입니다.

image-90.png 


인접 노드의 거리를 업데이트 한 후 다음을 수행해야 합니다.


  • 현재 알려진 거리를 기반으로 소스 노드에 가장 가까운 노드를 선택합니다.
  • 방문한 것으로 표시하십시오.
  • 경로에 추가하십시오.


거리 목록을 확인하면 노드 1이 소스 노드까지의 거리가 가장 짧다는 것을 알 수 있으므로 (거리 2) 경로에 추가합니다.


다이어그램에서 빨간색 가장자리로 이를 나타낼 수 있습니다.


image-94.png 


목록에서 빨간색 사각형으로 표시하여 "방문"되었으며 이 노드에 대한 최단 경로를 찾았음을 나타냅니다.


image-92.png 

방문하지 않은 노드 목록에서 제거합니다.


image-93.png 

이제 새로운 인접 노드를 분석하여 가장 짧은 경로를 찾아야 합니다. 이미 최단 경로 (빨간색 모서리로 표시된 경로)의 일부인 노드에 인접한 노드 만 분석합니다.


노드 3과 노드 2는 아래에서 볼 수 있듯이 각각 노드 0과 노드 1에 직접 연결되어 있기 때문에 이미 경로에 있는 노드에 인접 해 있습니다. 다음 단계에서 분석 할 노드입니다.


image-94.png 

이미 소스 노드에서 노드 2까지의 거리가 목록에 기록되어 있으므로 이번에는 거리를 업데이트 할 필요가 없습니다. 소스 노드에서 새 인접 노드 (노드 3)까지의 거리 만 업데이트하면 됩니다.


image-98.png 

이 거리는 7입니다. 이유를 살펴 보겠습니다.


소스 노드에서 다른 노드 (이 경우 노드 3)까지의 거리를 찾기 위해 해당 노드에 도달하는 최단 경로를 형성하는 모든 가장자리의 가중치를 추가합니다.


  • 노드 3의 경우 경로 0-> 1-> 3을 형성하는 가장자리의 가중치를 더하기 때문에 총 거리는 7입니다 (가장자리 0-> 1의 경우 2, 가장자리 1-> 3의 경우 5).

image-94.png 

이제 인접 노드까지의 거리가 있으므로 경로에 추가 할 노드를 선택해야 합니다. 소스 노드까지 가장 짧은 (현재 알려진) 거리를 가진 방문하지 않은 노드를 선택해야 합니다.


거리 목록에서 이것이 거리가 6 인 노드 2임을 즉시 감지 할 수 있습니다.


image-98.png 


노드 주위에 빨간색 테두리와 빨간색 가장자리를 사용하여 그래픽으로 경로에 추가합니다.


image-96.png 


또한 거리 목록에 작은 빨간색 사각형을 추가하고 방문하지 않은 노드 목록에서 교차하여 방문한 것으로 표시합니다.


image-99.png 

image-100.png 

이제 소스 노드에서 새 인접 노드 인 노드 3까지의 최단 경로를 찾기 위해 프로세스를 반복해야 합니다.


두 가지 가능한 경로가 있음을 알 수 있습니다. 0-> 1-> 3 또는 0-> 2-> 3. 가장 짧은 경로를 결정하는 방법을 살펴 보겠습니다.


image-96.png 

노드 3에는 이전에 기록 된 목록에 이미 거리가 있습니다 (7, 아래 목록 참조). 이 거리는 경로 0-> 1-> 3을 따르기 위해 교차해야 하는 두 모서리의 가중치 5와 2를 추가 한 이전 단계의 결과입니다.


하지만 이제 다른 대안이 있습니다. 경로 0-> 2-> 3을 따르도록 선택하면 총 거리 14를 나타내는 가중치 6과 8로 각각 0-> 2 및 2-> 3의 두 모서리를 따라야 합니다.


image-101.png 

분명히 첫 번째 (기존) 거리가 더 짧으므로 (7 대 14) 원래 경로를 유지하도록 선택합니다. 0-> 1-> 3. 새 경로가 더 짧은 경우에만 거리를 업데이트합니다.


따라서 첫 번째 대안 인 0-> 1-> 3을 사용하여 이 노드를 경로에 추가합니다.


image-104.png 

이 노드를 방문한 것으로 표시하고 방문하지 않은 노드 목록에서 제거합니다.


image-103.png 

image-106.png 

이제 우리는 과정을 다시 반복합니다.


지금까지 방문하지 않은 새로운 인접 노드를 확인해야 합니다. 이번에는 이러한 노드가 노드 3에 인접 해 있으므로 노드 4와 노드 5입니다.


image-104.png 

가능한 경우 항상 더 짧은 경로를 찾으려고 이러한 노드의 거리를 소스 노드로 업데이트합니다.


  • 노드 4의 경우 거리는 경로 0-> 1-> 3-> 4로부터 17입니다.
  • 노드 5의 경우 거리는 경로 0-> 1-> 3-> 5로부터 22입니다.

? 팁 : 최단 경로 (빨간색으로 표시) 확장 만 고려할 수 있습니다. 최단 경로에 추가되지 않은 가장자리를 통과하는 경로는 고려할 수 없습니다 (예 : 가장자리 2-> 3을 통과하는 경로를 형성 할 수 없음).


image-105.png 

지금 방문한 것으로 표시 할 방문하지 않은 노드를 선택해야 합니다. 이 경우 거리 목록에서 가장 짧은 거리가 있으므로 노드 4입니다. 다이어그램에 그래픽으로 추가합니다.


image-108.png 


또한 목록에 작은 빨간색 사각형을 추가하여 "방문 함"으로 표시합니다.


image-107.png 


그리고 방문하지 않은 노드 목록에서 제거합니다.


image-109.png 

그리고 우리는 과정을 다시 반복합니다. 인접 노드 인 노드 5와 노드 6을 확인합니다. 이미 방문한 것으로 표시되고 경로에 추가 된 노드에서 도달하기 위해 따라갈 수 있는 각 가능한 경로를 분석해야 합니다.


image-108.png 

노드 5의 경우 :


  • 첫 번째 옵션은 경로 0-> 1-> 3-> 5를 따르는 것입니다. 경로는 소스 노드에서 22 (2 + 5 + 15) 거리에 있습니다. 이 거리는 이전 단계의 거리 목록에 이미 기록되어 있습니다.
  • 두 번째 옵션은 경로 0-> 1-> 3-> 4-> 5를 따르는 것입니다.이 경로는 소스 노드 (2 + 5 + 10 + 6)에서 23의 거리를 갖습니다.


분명히 첫 번째 경로는 더 짧으므로 노드 5에 대해 선택합니다.


노드 6의 경우 :

  • 사용 가능한 경로는 0-> 1-> 3-> 4-> 6이며 소스 노드 (2 + 5 + 10 + 2)에서 19의 거리를 갖습니다.

image-110.png 

방문한 최단 거리 (현재 알려진)로 노드를 표시합니다. 이 경우 노드 6입니다. 


image-140.png 


그리고 방문하지 않은 노드 목록에서 제거합니다. 



image-111.png 


이제 이 경로 (빨간색으로 표시됨)가 있습니다. 


image-112.png 

아직 하나의 노드 (노드 5) 만 방문하지 않았습니다. 경로에 어떻게 포함 시킬 수 있는지 살펴 보겠습니다. 


경로에 추가 된 노드에서 노드 5에 도달하기 위해 취할 수 있는 세 가지 경로가 있습니다.


  • 옵션 1 : 0-> 1-> 3-> 5 (거리 22 (2 + 5 + 15)).
  • 옵션 2 : 0-> 1-> 3-> 4-> 5, 거리 23 (2 + 5 + 10 + 6).
  • 옵션 3 : 0-> 1-> 3-> 4-> 6-> 5, 거리 25 (2 + 5 + 10 + 2 + 6).

image-113.png 

최단 경로를 선택합니다 : 거리가 22 인 0-> 1-> 3-> 5.


image-115.png 


노드를 방문한 것으로 표시하고 방문하지 않은 노드 목록에서 제거합니다.


image-114.png 

image-116.png 


그리고 voilà! 그래프의 노드 0에서 각 노드까지의 최단 경로로 최종 결과를 얻었습니다.


image-115.png 

다이어그램에서 빨간색 선은 최단 경로에 속하는 가장자리를 표시합니다. 노드 0에서 시작하는 그래프의 주어진 노드에 도달하기 위해 최단 경로를 따라 가려면 이러한 간선을 따라야 합니다.


예를 들어, 노드 0에서 시작하여 노드 6에 도달하려면 빨간색 가장자리 만 따라 가면 최단 경로 0-> 1-> 3-> 4-> 6을 자동으로 따라갑니다.


? 요약 


  • 그래프는 개체, 사람 또는 개체 간의 연결을 모델링 하는 데 사용됩니다. 여기에는 노드와 모서리의 두 가지 주요 요소가 있습니다. 노드는 개체를 나타내고 가장자리는 이러한 개체 간의 연결을 나타냅니다.
  • Dijkstra의 알고리즘은 주어진 노드 ( "소스 노드"라고 함)와 그래프의 다른 모든 노드 사이의 최단 경로를 찾습니다.
  • 이 알고리즘은 가장자리의 가중치를 사용하여 소스 노드와 다른 모든 노드 사이의 총 거리 (가중치)를 최소화하는 경로를 찾습니다.

내 기사가 마음에 들고 도움이 되었기를 바랍니다. 이제 Dijkstra의 알고리즘이 무대 뒤에서 어떻게 작동하는지 알게 되었습니다. Twitter @EstefaniaCassN에서 저를 팔로우 하고 제 온라인 코스를 확인하십시오.