반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 9: 최단 경로 알고리즘 심화 (벨만-포드, 존슨 알고리즘) 최단 경로 알고리즘최단 경로 알고리즘은 가중치 그래프에서 주어진 두 정점 간의 최단 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 그리고 존슨 알고리즘(Johnson's Algorithm)이 있습니다.오늘은 벨만-포드 알고리즘과 존슨 알고리즘에 대해 심화 학습하겠습니다.벨만-포드 알고리즘 (Bellman-Ford Algorithm)벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 알고리즘입니다. 그러나 음의 사이클이 있는 경우에는 사용할 수 없습니다.벨만-포드 알고리즘의 시간 복잡도:(O(VE)), 여기서 (V)는 정점의 수, (E)는 간선의 수입.. 2024. 8. 1. [알고리즘] 8. 최단 경로 알고리즘 Index 1. 최단 경로 문제 2. 다익스트라 최단 경로 3. 플로이드 워셜 4. 벨만 포드 5. 추천 문제 6. 참고자료1. 최단 경로 문제최단 경로 문제- 가장 짧은 경로를 찾는 알고리즘- 각 지점은 그래프에서 node로 표현, 지점 간 연결된 도로는 edge로 표현 (최단 경로 유형)- 한 지점에서 다른 한 지점까지의 최단 경로- 한 지점에서 다른 모든 지점까지의 최단 경로- 모든 지점에서 다른 모든 지점까지의 최단 경로 2. 다익스트라 최단 경로Djikstra- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산- 음의 간선이 없을 때 정상적으로 동작- 매 상황에서 방문하지 않은 가장 적은 비용이 드는 노드를 선택(그리디)- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 .. 2024. 7. 20. 이전 1 다음 반응형
