그래프 알고리즘

방향 비순환 그래프(DAG)에서 모든 간선이 앞에서 뒤로만 향하도록 정점을 일렬로 나열합니다. Kahn 알고리즘은 진입차수(indegree)가 0인 노드를 큐로 관리하며 차례로 출력해, 작업 스케줄링·의존성 해소·빌드 순서 결정의 기반이 됩니다.

음수 간선이 없는 가중치 그래프에서 시작 노드로부터의 최단 거리를 구합니다. 우선순위 큐로 매번 거리가 가장 작은 노드를 확정하고 이웃을 완화(relax)하는 그리디 전략으로, 내비게이션·네트워크 라우팅의 표준입니다.

음수 간선이 있어도 동작하는 최단 경로 알고리즘입니다. 모든 간선을 V−1번 반복 완화하면 최단 거리가 수렴하며, 한 번 더 완화되면 음수 사이클이 존재함을 검출합니다. 다익스트라보다 느리지만 더 일반적입니다.

모든 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선만 차례로 채택해 최소 신장 트리(MST)를 만듭니다. 사이클 판별은 유니온-파인드(Union-Find)로 O(α)에 처리합니다.

한 노드에서 시작해 트리에 연결된 가장 싼 간선을 하나씩 더해 가며 최소 신장 트리를 키웁니다. 우선순위 큐로 후보 간선을 관리하며, 크루스칼과 다른 순서로 자라지만 동일한 MST에 도달합니다.