Introduction
Coddy의 벨만-포드 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 1번째.
그래프 알고리즘 시리즈에 다시 오신 것을 환영합니다! 다익스트라(Dijkstra)는 빠르지만, 간선이 음수일 수 있는 경우에는 제대로 작동하지 않습니다. 벨만-포드(Bellman-Ford) 알고리즘은 음수 가중치를 처리할 수 있으며, 그래프에 음수 사이클이 있는지도 알려줄 수 있습니다.
다익스트라와 마찬가지로, 단일 출발점으로부터의 최단 거리를 찾습니다. 그래프는 n (정점 0부터 n - 1까지)과 가중치 w인 유향 간선 u -> v에 대한 트리플(triples) [u0, v0, w0, ...]의 평면 배열인 edges로 주어집니다 (가중치는 음수일 수 있습니다).
도달할 수 없는 정점은 -1로 보고됩니다. 시작해 봅시다!
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
