[java] 최단 경로 알고리즘의 시간 복잡도
최단 경로 알고리즘은 그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 알고리즘입니다. 이러한 알고리즘은 다양한 방법으로 구현할 수 있으며, 각 알고리즘마다 시간 복잡도가 다를 수 있습니다.
다익스트라 알고리즘 (Dijkstra’s Algorithm)
다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 그리디 알고리즘의 일종으로, 각 정점까지의 최단 거리를 구하고 이를 기준으로 다음에 방문할 정점을 선택합니다.
다익스트라 알고리즘의 시간 복잡도는 힙(heap)을 사용하는 경우 O((V + E)logV)입니다. V는 정점의 수, E는 간선의 수입니다.
벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드 알고리즘은 음수 가중치가 포함된 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과 달리, 음수 가중치를 처리할 수 있습니다.
벨만-포드 알고리즘의 시간 복잡도는 O(VE)입니다. V는 정점의 수, E는 간선의 수입니다.
플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)
플로이드-와샬 알고리즘은 그래프의 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다이나믹 프로그래밍의 일종으로, 모든 정점을 중간 경로로 고려하여 최단 경로를 갱신합니다.
플로이드-와샬 알고리즘의 시간 복잡도는 O(V^3)입니다. V는 정점의 수입니다.