이제 우리가 가장 친숙한 가중치 그래프의 응용이 나올건데
바로바로 최단경로( shortest path) 를 배울겁니다.
보통 최단 거리, 최소 시간, 최소 비용 등등 뭐 가중치마다 다르게 설정되니까 각각 알아내면 되겠지?
아무튼 얘가 우리가 실생활에서 접하는 진짜 필요한거지 ㅋㅋㅋ
이런식으로 설정되어 있다면,,?
- 경로1: (A,B,C,D): 비용 = 7 + 4 + 2 = 13
- 경로2: (A,E,B,C,D): 비용 = 3 + 2 + 4 + 2 = 11
- 경로3: (A,F,B,D): 비용 = 10 + 6 + 10 = 26
경로1이 최소비용을 가진 경로고 사용자에게 추천을 하겠지??
이제 들어가기 전에!
여기에도 MST와 비슷하게 2가지 알고리즘이 있어,,,
우선 이름을 알아보자면 Dijkstra 와 Floyd 2가지가 있고 오늘은 하나만 해볼거야
이번에는 저 Dijkstra 에 대해서 배워볼건데 솔직히 못 읽겠다 그지? ㅋㅋㅋㅋ 어차피 이름이 중요한게 아니라 알고리즘이 중요한거니까 넘어가자
이 방법은 시작 정점 v(임의)에서 모든 다른 정점까지의 최단 경로 찾는 것이야.
그렇다면 먼저 알아야할게 필요해
가정: 가중치는 반드시 양수
집합 S: v에서부터의 최단경로가 이미 발견된 정점들의 집합
dist 배열: 최단경로가 알려진 정점들을 이용한 다른 정점들까지의 최단경로 길이
//Prim 에서랑 비슷하다.
시작정점 v, 다른 정점들 u
초기값으로는
dist[v] = 0
dist[u] = 시작정점 v와 u간의 가중치 값
매 단계에서 최소 distance인 정점을 S에 추가 // 최소거리만 추가해도 괜찮을까...? 의문이 들 수 있지 ㅇㅇㅇ그렇지
흠 그렇다면 다음 그림을 보고 생각해보자 그 의문도 풀어보고
사실 나는 의문따윈 들지 않았지 당연한거라 생각해서 ㅋㅋㅋㅋ
u로 가는 최단거리가 2+3이 될 수가 있을까..? 1보다 작은 가중치 값을 가질 수 있을까?
w로 가는 가중치가 더 작았다고 하더라도 w의 가중치가 가장 작아져버리면 w가 1번:최단경로가 되버리는
모순인 상황이 생기고 3번이 음수라면 모를까.. 절대 그럴 수 없다. 또한 조건에 가중치는 음수를 허용하지 않는다.
즉
distance 값이 가장 작은 정점이 u
v에서 u까지의 최단경로는 ①
경로 ②는 ①보다 항상 길 수 밖에 없음.
Why? ③ 은 항상 양수이므로…
따라서 매 단계에서 distance 값이 가장 작은 정점들을 추가하면 모든 정점까지의 최단거리를 구할 수 있다
또한 새로운 정점이 S에 추가된다면 또 distance는 바뀌어야만 한다. 그래서 경유지 설정하면 경로도 바뀌잖아 ㅋㅋㅋ
이런식으로 갱신시킨다.
그래서 이걸 종합적으로 다 합치면 어떤 알고리즘이 나오느냐?
이러한 알고리즘이 나온다 이말이다.
그러면 그림으로 또 알아보자. 코드는 그 다음에
초기 상태 집합 S에는 정점 A만 들어있다. 그래서 거리가 저렇게 되는 것이다.
이제 가장 distance가 작은 정점 E를 S에 추가시킨다.
S에 포함되지 않은 distance를 다시 갱신해준다.
반복반복
반복반복
반복반복
반복반복
완성!!!ㅋㅋㅋㅋㅋㅋ 저런식으로 다 이어버렸다. a에서 갈수있는 모든 정점 최단거리가 나왔다.
정말 유용하네요!!! 이제,,, 지옥의 코드분석 하러가보자 ㅎㅎ
후.. 힘들다... 이렇게 반복문이 많아서 원,,
그래서 시간복잡도를 본다면
네트워크에 n개의 정점이 있을 때
–주 반복문을 n번 반복
–내부 반복문을 2n번 반복
결국 O(n^2)의 시간복잡도를 가짐 끗
ㅎㅎㅎㅎ
Floyd는 다음에ㅎㅎ