별의 공부 블로그 🧑🏻‍💻

🗒️ Shortest Path Problem (2)

728x90
  1. 2021.07.02 벨만-포드 알고리즘(Bellman-Ford Algorithm)

    벨만-포드 알고리즘(Bellman-Ford Algorithm) 음수 가중치가 있는 그래프를 다룰 때 사용하는 알고리즘 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾음. V : 정점의 개수 다익스트라 알고리즘보다 높은 점근적 시간 복잡도를 가짐. 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공함. 코드 1 음수 가중치 사이클 이 없을 경우 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edge..

  2. 2021.06.30 다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)

    다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm) 그래프에서 단일 시작(Single Start) 최단 경로 문제(Shortest Path Problem) 구글 지도 또는 자동차 내비게이션 등에서 경로를 탐색할 때 사용됨. 문제 정의 주어진 그래프 G = 의 시작 정점(Source Vertex) 과 목적 정점(Destination Vertex) 이 주어질 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하시오. V : 정점의 집합 E : 에지의 집합 각각의 에지는 가중치를 가지고 있음. 다익스트라 알고리즘(Dijkstra's Algorithm) 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘 프림의 MST 알고리즘을 약간 변경한 형태 ..

728x90
📖 Contents 📖

티스토리툴바