벨만포드2 [알고리즘] 벨만 포드 알고리즘 (Bellman-Ford) Bellman-Ford Algorithm 이 알고리즘은 모든 간선을 전부 확인하여, 음수 가중치도 문제도 해결할 수 있습니다. 1. 엣지 리스트를 활용한다. 위에 언급한 것처럼, '모든 간선(엣지)'를 전부 확인함으로 엣지 리스트를 사용하는 편이 직관적이고 효율적입니다. 엣지 리스트란, 단순하게 모든 엣지 정보(시작 노드, 도착 노드, 비용)을 담은 리스트입니다. 2. 'update'를 노드의 개수 - 1번 만큼 반복한다. 우선, 다익스트라에서 사용한 것과 유사하게, 최소 비용 배열을 선언한 후, 모두 무한의 값으로 초기화합니다. (최소비용배열[N] = 시작 노드에서 출발하여 N번 노드로 가는 최소비용) 이 배열의 시작 노드 값을 0으로 설정합니다. 이제 Update는 아래와 같습니다. 엣지 리스트를 순.. 2023. 1. 13. [알고리즘] BFS와 다익스트라 알고리즘 들어가며 오늘은 그래프에서 최단 경로를 찾는 방법에 대해 정리해보려합니다. 정리 상황에 맞는 알고리즘을 잘 정리해둔 것을 보아서 가져와봤습니다. 단일 node - 단일 node 모든 node쌍 Edge에 weight 없음 Breadth First Search (BFS) Floyd-Warshall Algorithm Edge에 weight 있음 음수 weight 있음 Bellman-Ford Algorithm 음수 weight 없음 Dijkstra Algorithm 출처: https://shnoh.tistory.com/15 BFS (너비 우선 탐색) 가장 단순한 형태입니다. weight가 없으니 depth가 곧 거리가 될 것이기 떄문에, 한 depth를 모두 살핀 후 그 다음 depth를 탐색하는 BFS를 통.. 2023. 1. 13. 이전 1 다음