시냅스

플로이드 알고리즘 Floyd algorithm 모든 지점에서 모든 지점으로의 최단 경로를 모두 구하는 경우 꼭짓점 k를 두고, k를 경유할 경우를 원래의 값과 비교하여 더 짧다면 업데이트 한다. (i,j) > (i,k) + (k,j) 와 같은 꼴이다. 다이나믹 프로그래밍 기술에 의거한다. 구현이 쉽고 간단하지만 O(n^3) 시간복잡도가 높다. 구현 int INF = 99999999; int **arr_init(LinkedGraph *graph) { int **arr = calloc(graph->currentVertexCount, sizeof(int *)); ListNode *temp; for(int i = 0; i currentVertexCount; i++) arr[i] = calloc(..

다익스트라 알고리즘 Dijkstra algorithm 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 방식 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식을 소개 구현 방식 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨 1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정..

프림 알고리즘 Prim algorithm 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중..

크루스칼 알고리즘 Kruskal algorithm 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점 사이 사이클이 발생하지 않으면(DFS) 정점을 연결한다. 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) c언어로 구현 간선 가중치를 최소 값으로 오름차순 정렬 dfs를 통해 사이클을 갖고 있는지 확인 Heap *sorted_heap(LinkedGraph *graph) // 간선의 가중치를 기준으로 최소로 정렬한다. // 여기에선 key가 가중치가 된다. { Heap *temp = createHeap(graph->currentEdgeCount); ListNod..