✨그래프 알고리즘 비교✨

알고리즘 클릭 시, 해당 페이지로 이동

정점 중심 구현

최단 경로: 두 노드 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘

• 다익스트라 알고리즘 : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 O(ElogV)
• 플로이드 워셜 알고리즘 : 모든 노드에서 다른 모든 노드의 최단 경로 O(V3)

최소 신장 트리(MST): 최소한의 비용으로 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프

• 프림 알고리즘 : 시작 노드에서 가까운 노드를 선택하여 트리 구성 ➜ 사이클 검사X O(V2)

간선 중심 구현

최단 경로

• 벨만포드 알고리즘 : 음의 가중치를 허용

최소 신장 트리(MST)

• 크루스칼 알고리즘 : 최소 비용의 간선을 차례대로 대입하여 트리를 구성 ➜ 사이클 검사必 O(ElogE)

간선의 개수가 적은 경우에는 크루스칼 알고리즘이 유리, 간선의 개수가 많은 경우에는 프림 알고리즘이 유리