기록기록 우는 갈매기

다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제이다. 앞서 살펴본 프림 알고리즘, 크루스칼 알고리즘과 마찬가지로 최단 경로를 구하는 문제이며 그래프를 사용한다는 점에서 공통점이 있지만 다익스트라 알고리즘은 Minimum Spanning Tree를 구하는 문제가 아니라는 점에서 차이가 있다. 아래의 수도코드를 보면 프림 알고리즘의 수도코드와 유사하다는 것을 알 수 있지만, 이미 방문한 집합 V-Y에서부터 정점 v까지의 최단거리를 선택하는 프림 알고리즘과 달리 다익스트라 알고리즘은 출발점부터 정점 v까지의 최단거리를 구한다. 수도코드(high level) F:=∅ Y:={v1}; while(the instance is not solved..

크루스칼 알고리즘은 프림 알고리즘과 달리 한 정점이 locally optimal한지 결정할 때 단순히 edge의 가중치를 기준으로 결정한다. 즉, edge의 가중치가 작으면 작을수록 locally optimal한 것이다. 가중치가 작은 것 부터, 즉 유리한 것 부터 먼저 담으려는 크루스칼 알고리즘의 의도가 참 말그대로 'Greedy' 해보인다. 하지만 크루스칼 알고리즘이 대책없이 edge들을 마구마구 담아대는 것은 아니다. 순환 경로가 발생하지 않도록 정점들의 관계를 검사하는 작업을 치른다. 이 과정에 대해 더 자세히 알아보도록 하자. 수도코드(high level) F := ∅; //edge의 집합 초기화 create disjoint subsets of V, one for each vertex and c..