Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

<시간/>

정의

Dijkstra의 알고리즘은 소스 노드라고 하는 특정 노드에서 연결된 그래프의 다른 모든 노드까지의 최단 경로를 찾습니다. 소스 노드를 루트로 하는 최단 경로 트리를 생성합니다. 라우팅 비용을 최소화하기 위해 최적의 경로를 생성하기 위해 컴퓨터 네트워크에서 많이 사용됩니다.

다익스트라의 알고리즘

입력 - 네트워크를 나타내는 그래프. 및 소스 노드, s

출력 - s가 루트 노드인 최단 경로 트리 spt[].

초기화 -

  • dist[] 거리 배열 |V| 크기 (노드 수), 여기서 dist[s] =0 및 dist[u] =∞(무한대), 여기서 u는 s를 제외한 그래프의 노드를 나타냅니다.

  • 배열, Q , 그래프의 모든 노드를 포함합니다. 알고리즘이 완료되면 Q 비어 있게 됩니다.

  • 빈 세트, S , 방문한 노드가 추가됩니다. 알고리즘이 완료되면 S 그래프의 모든 노드를 포함합니다.

  • Q 동안 반복 비어 있지 않습니다 -

    • Q에서 삭제 , 노드, u가 가장 작은 dist[u] 그리고 이것은 S에 없습니다. 첫 번째 실행에서 dist[s] 제거됩니다.

    • S에 u를 추가하여 방문한 것으로 표시합니다.

    • u에 인접한 각 노드 v에 대해 dist[v]를 -

      로 업데이트합니다.

      • 만약 (dist[u] + 모서리 u-v의 가중치 ) 그럼

        • 업데이트 dist[v] =dist[u] + edge u-v의 가중치

  • 배열 dist[] s에서 다른 모든 노드까지의 최단 경로를 포함합니다.

예시

알고리즘의 작동은 예제를 사용하여 가장 잘 이해할 수 있습니다. A에서 G로 표시된 노드가 있는 다음 그래프를 고려하십시오. 다음과 같이 가중 간선으로 연결됩니다. -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

초기화는 다음과 같습니다 -

  • dist[7]={0,∞,∞,∞,∞,∞,∞}

  • Q={A,B,C,D,E,F,G}

  • S𝑆=∅

통과 1 − 노드 A를 선택합니다. Q에서 가장 낮은 dist[]를 가지고 있기 때문에 0 값 그리고 그것을 S에 넣습니다. A의 이웃 노드는 B와 C입니다. 우리는 알고리즘에 따라 B와 C에 해당하는 dist[] 값을 업데이트합니다. 따라서 데이터 구조의 값은 -

가 됩니다.

  • dist[7]={0,5,6,∞,∞,∞,∞}

  • Q={B,C,D,E,F,G}

  • S={A}

이 패스 이후의 거리와 최단 경로는 다음 그래프에 나와 있습니다. 녹색 노드는 이미 S −

에 추가된 노드를 나타냅니다.

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

통과 2 − 노드 B를 선택합니다. Q에서 가장 낮은 dist[]를 가지고 있기 때문에 5의 값 그리고 S.에 넣으세요. B의 인접 노드는 C, D입니다. 및 E . C, D 에 해당하는 dist[] 값을 업데이트합니다. 그리고 알고리즘에 따른 E. 따라서 데이터 구조의 값은 -

가 됩니다.

  • dist[7]={0,5,6,12,13,∞,∞}

  • Q={C,D,E,F,G}

  • S={A,B}

이 통과 후의 거리와 최단 경로는 -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

패스 3 − 노드 C를 선택합니다. Q에서 가장 낮은 dist[] 값이 6이므로 S에 넣습니다. C의 인접 노드는 D와 F입니다. D와 F에 해당하는 dist[] 값을 업데이트합니다. 따라서 데이터 구조의 값은 -

  • dist[7]={0,5,6,8,13,10,∞}

  • Q={D,E,F,G}

  • S={A,B,C}

이 통과 후의 거리와 최단 경로는 -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

4 통과 − 노드 D를 선택합니다. Q에서 가장 낮은 dist[ ] 값을 8로 지정하고 S에 넣습니다. D의 인접 노드는 E, F 및 G입니다. dist[] 를 업데이트합니다. E, F에 해당하는 값 및 G . 따라서 데이터 구조의 값은 -

가 됩니다.

  • dist[7]={0,5,6,8,10,10,18}

  • Q={E,F,G}

  • S={A,B,C,D}

이 통과 후의 거리와 최단 경로는 -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

5 통과 − 노드 E 또는 노드 F를 선택할 수 있습니다. Q에서 둘 다 가장 낮은 dist[]를 가지고 있기 때문에 10 값 . 우리는 그들 중 하나를 선택합니다. E , 그리고 S에 넣습니다. . D의 인접 노드 G입니다. . dist[] 업데이트 G에 해당하는 값. 따라서 데이터 구조의 값은 -

가 됩니다.

  • dist[7]={0,5,6,8,10,10,13}

  • Q={F,G}

  • S={A,B,C,D,E}

이 통과 후의 거리와 최단 경로는 -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

패스 6 − 노드 F를 선택합니다. Q에서 가장 낮은 dist[] 를 가지고 있기 때문에 10 값 S에 넣어 . F의 인접 노드 G입니다. . 거리[] G에 해당하는 값은 F를 통한 값보다 작습니다. . 따라서 동일하게 유지됩니다. 데이터 구조의 값은 -

가 됩니다.

  • dist[7]={0,5,6,8,10,10,13}

  • Q={G}

  • S={A,B,C,D,E,F}

이 통과 후의 거리와 최단 경로는 -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘

7 통과 − Q에는 노드가 하나만 있습니다. . Q에서 삭제합니다. 그것을 S에 넣으십시오. dist[] 배열은 변경할 필요가 없습니다. 이제 Q 비어 있게 됨, S 모든 노드를 포함하므로 알고리즘의 끝에 도달합니다. 경로의 경로에 없는 모든 모서리 또는 경로를 제거합니다. 따라서 소스 노드 A에서 다른 모든 노드까지의 최단 경로 트리는 다음과 같습니다. -

그래프를 통해 최단 경로를 계산하는 다익스트라 알고리즘