반응형 [C++로 배우는 알고리즘과 자료구조] Day 25: 다익스트라 알고리즘 (Dijkstra's Algorithm) 다익스트라 알고리즘 (Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 단일 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 그래프에서 작동합니다.다익스트라 알고리즘의 시간 복잡도:일반적인 구현: (O(V^2))우선순위 큐를 사용한 구현 (힙): (O((V + E) \log V))다익스트라 알고리즘 구현그래프 구현 (인접 리스트 사용)#include #include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int u, int v, int weight); // 간선 추가 vo.. 2024. 8. 1. [알고리즘] 8. 최단 경로 알고리즘 Index 1. 최단 경로 문제 2. 다익스트라 최단 경로 3. 플로이드 워셜 4. 벨만 포드 5. 추천 문제 6. 참고자료1. 최단 경로 문제최단 경로 문제- 가장 짧은 경로를 찾는 알고리즘- 각 지점은 그래프에서 node로 표현, 지점 간 연결된 도로는 edge로 표현 (최단 경로 유형)- 한 지점에서 다른 한 지점까지의 최단 경로- 한 지점에서 다른 모든 지점까지의 최단 경로- 모든 지점에서 다른 모든 지점까지의 최단 경로 2. 다익스트라 최단 경로Djikstra- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산- 음의 간선이 없을 때 정상적으로 동작- 매 상황에서 방문하지 않은 가장 적은 비용이 드는 노드를 선택(그리디)- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 .. 2024. 7. 20. 이전 1 다음 반응형
