search

2d3k / CS-Study

기본을 소홀히 하지 말자!!
0 stars 1 forks source link

[Data Structure] 최단거리 알고리즘 #25

Open 2d3k opened 1 year ago

2d3k commented 1 year ago

다익스트라와 밸만포드의 특징?

둘의 차이?

2d3k commented 1 year ago

다익스트라 알고리즘은 가장 가까운 정점부터 탐색하며 최단 경로를 구합니다. 간선의 가중치가 음수인 경우에는 사용할 수 없습니다. 이 알고리즘의 시간 복잡도는 O(|E| + |V|log|V|) 입니다. 이 때 E는 간선의 개수, V는 정점의 개수입니다. 다익스트라 알고리즘은 일반적으로 우선순위 큐를 사용하여 구현합니다.

반면에 벨만-포드 알고리즘은 간선의 가중치가 음수인 경우에도 사용할 수 있습니다. 이 알고리즘은 모든 간선을 V-1번 순회하여 최단 경로를 찾습니다. 이 알고리즘의 시간 복잡도는 O(|E||V|) 입니다. 이 알고리즘은 다익스트라 알고리즘과 달리 큐를 사용하지 않고, 간단한 반복문으로 구현할 수 있습니다.

따라서, 다익스트라 알고리즘은 간선의 가중치가 양수일 때, 더 빠른 실행 시간을 보이며, 벨만-포드 알고리즘은 음수 가중치가 있을 때 사용할 수 있습니다.

hyeonayou commented 1 year ago

  1. 다익스트라 알고리즘은 그래프 상에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 다르게 표현하면 가중 그래프에서 간선 가중치의 합의 최소가 되는 경로를 찾는 알고리즘 중 하나다. V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘

벨만 포드 알고리즘은 동작원리는 다익스트라와 유사하다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며 시간 복잡도가 O(VE) 입니다. (V: 정점 개수, E: 간선 개수)