[C언어] 자료구조 - 가중치 그래프 Weighted Graph + Floyd -4

저번 글을 너무 힘들게 써가지고,, 이건 좀 간단하게 해야 것습니다.

 

앞에 배운 Dijkstra와의 차이점은 얘는 실행하면

모든 정점사이의 최단경로를 한꺼번에 찾아준다는 것인디

 

어떻게 구성하느냐?

 

2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성 하는데

이게 무슨말이냐 하면은 그냥 반복한다는 것이다.ㅋㅋ

 

•배열 A의 초기 값은 인접 행렬 weight

•인접 행렬 weight 구성

1. i==j이면, weight[i][j]=0

2. 두 정점 i, j 사이에 간선이 존재하지 않으면, weight[i][j]=∞

3. i, j 사이에 간선이 존재하면, weight[i][j]는 간선 (i, j)의 가중치

 

말보다 더 간단히 하자면

이런식이라는 것인데 조금 어려울 수 있으니 풀어서 설명해보자면

 

Ak  [i][j]: 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로 길이

즉 A-1→A0 → A1 → … → An-1 순으로 최단 경로 구해가는 것이다.

물론 A-1는 weight의 배열 값과 같다. ㅎㅎ

 

저런식 알겠나??? ㅋㅋㅋㅋ 책에서는 이렇게 표현하기도 했다.

무슨 말인지 헷갈릴 수 있는데

 펼쳐서 설명해보자면 k의 정점까지 이용해야하는데, k의 정점을 이용하지 않은 값이 최솟값과 이용해서 최솟값이 되는 것 2개를 구분해야한다는 것이다. 이거 그 순열 조합 때 비슷하게 배우는 것 하나있는데ㅋㅋㅋ  까먹음 ㅎ

 

그렇지만 여기서는 가짓수를 따지는 것이 아니기 때문에 1,2 중 작은 값이 답이 되시겠다.

 

그림으로 살짝쿵 봤으니까 코드로 볼까? ㅋㅋㅋㅋㅋㅋ

 

 

그렇게 출력함수를 가져다 놓은 결과를 보자면
이러한 그래프를 탐색한것이다

 

 

그렇게 나오더라

 

근데 어차피 Dijkstra를 돌리면 다 나올거 왜 얘는 돌리냐 하는 사람도 있을 수 있다. 

 

모든 정점쌍의 최단경로를 구하려면 Dijkstra의 알고리즘 O(n2)을 n번 반복해도 되지만 이 경우 전체 복잡도는 O(n3) 이 된다 어차피 똑같은거다 ㅋㅋㅋ 그렇지만!!!!

 

모든 정점쌍의 최단경로를 구하는데 있어 두 알고리즘 모두  동일한 O(n3)의 복잡도를 가지지만

Floyd의 알고리즘은 간결한 반복구문을 사용하므로 Dijkstra의 알고리즘 보다 효율적이다.

 

걍 코드 짜기 쉽다고 ㅎㅎ 그럼 이만 ㅃㅃㅃ