컴퓨터 네트워크의 최단 경로 알고리즘

컴퓨터 네트워크에서 최단 경로 알고리즘은 라우팅 비용이 최소화되도록 네트워크 노드 간의 최적 경로를 찾는 것을 목표로 합니다. 그래프 이론에서 제안하는 최단 경로 알고리즘을 직접 적용한 것입니다.

설명

네트워크가 M 에지(전송 라인)에 의해 연결된 N 정점(노드 또는 네트워크 장치)으로 구성되어 있다고 가정합니다. 각 에지는 전송 라인의 물리적 거리 또는 전송 지연을 나타내는 가중치와 연결됩니다. 최단 경로 알고리즘의 목표는 가장자리를 따라 정점 쌍 사이의 경로를 찾는 것이므로 가장자리 가중치의 합이 최소입니다. 에지의 가중치가 같으면 최단 경로 알고리즘은 최소 홉 수를 갖는 경로를 찾는 것을 목표로 합니다.

공통 최단 경로 알고리즘

몇 가지 일반적인 최단 경로 알고리즘은 다음과 같습니다. -

• 벨만 포드의 알고리즘

• 다익스트라 알고리즘

• Floyd Warshall의 알고리즘

다음 섹션에서는 이러한 각 알고리즘에 대해 설명합니다.

벨만 포드 알고리즘

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

출력 - s에서 다른 모든 노드까지의 최단 경로

• s에서 모든 노드까지의 거리를 무한(∞)으로 초기화합니다. 자신과의 거리를 0으로, 배열 dist[] |V| 크기 (노드 수) dist[s]를 제외한 모든 값이 ∞인 경우 .

• 최단 거리를 반복적으로 계산합니다. |V|- 1 반복 s −

  를 제외한 각 노드의 시간

  • 꼭짓점 u와 v -

    를 연결하는 각 모서리에 대해 반복합니다.

    • dist[v]인 경우> (dist[u] + edge u-v의 가중치) , 그럼

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

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

다익스트라의 알고리즘

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

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

초기화 -

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

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

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

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

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

  • u 추가 S로 , 방문한 것으로 표시합니다.

  • 각 노드 v에 대해 u에 인접 , 업데이트 dist[v] -

    로

    • (dist[u] + edge u-v의 가중치)인 경우 <거리[v] , 그럼

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

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

플로이드 워샬 알고리즘

입력 - 비용 인접 행렬, adj[][] , 네트워크의 노드 간 경로를 나타냅니다.

출력 - 최단 경로 비용 행렬, 비용[][] , 그래프의 각 노드 쌍 간의 비용 측면에서 최단 경로를 보여줍니다.

• 비용[][] 채우기 다음과 같이:

  • 수정[][]인 경우 비어 있는 경우 비용[][] =∞(무한)

  • 기타 비용[][] =수정[][]

• N =|V| , 여기서 V 네트워크의 노드 집합을 나타냅니다.

• k =1 ~ N에 대해 반복 -

  • i =1 ~ N에 대해 반복 -

    • j =1 ~ N에 대해 반복 -

      • 비용[i][k] + 비용[k][j]인 경우 <비용[i][j] , 그럼

        • 비용[i][j] 업데이트 :=비용[i][k] + 비용[k][j]

• 매트릭스 비용[][] 각 노드에서 가장 짧은 비용을 포함합니다. i , 다른 모든 노드로, j .