그래프 알고리즘: 최단 경로와 최소 신장 트리(MST)

네트워크의 모든 노드를 최소 비용으로 연결하는 방법부터, 목적지까지의 가장 빠른 길을 찾는 다양한 최단 경로 알고리즘들을 총정리합니다.

1. 최소 신장 트리 (Minimum Spanning Tree, MST)

모든 정점을 연결하되, 간선들의 가중치 합을 최소로 만드는 트리 구조입니다. 사이클이 없어야 한다는 점이 핵심입니다.

• 크루스칼 (Kruskal): 간선들을 가중치 순으로 정렬한 뒤, 사이클을 만들지 않는 선에서 작은 간선부터 차례로 선택합니다. (Greedy 방식)
• 프림 (Prim): 하나의 정점에서 시작하여 연결된 간선 중 가장 비용이 적은 정점을 선택하며 트리를 확장해 나갑니다.

2. 최단 경로 알고리즘 (Shortest Path)

특정 출발점에서 목적지까지 가중치의 합이 최소가 되는 경로를 찾습니다.

• 다익스트라 (Dijkstra): 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾습니다. 음수 가중치가 없을 때 사용하며 가장 대중적입니다.
• 벨만-포드 (Bellman-Ford): 음수 가중치가 있는 그래프에서도 동작하지만 속도가 느립니다. 음수 사이클 존재 여부도 확인할 수 있습니다.
• 플로이드-워셜 (Floyd-Warshall): '모든 정점' 사이의 최단 경로를 한 번에 구합니다. 3중 반복문을 사용하는 동적 계획법 방식입니다.

3. 위상 정렬 (Topological Sort)

순서가 있는 작업을 나열할 때 사용합니다. 선수 과목 이수 체계나 작업 스케줄링 등이 대표적인 예입니다. 사이클이 없는 방향 그래프(DAG)에서만 가능하며, 진입 차수가 0인 노드부터 차례로 제거하며 순서를 결정합니다.