10000COW

벨만-포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 음의 가중치를 갖는 edge(간선)이 있을 때 사용하는 알고리즘이다. 다익스트라 알고리즘과 차이는 무엇인가? 다익스트라 알고리즘 - 매번 방문하지 않는 노드 중에서 최단거리가 가장 짧은 노드를 선택해 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge(간선)이 없다면 최적의 해를 찾을 수 있다. - 시간 복잡도가 빠르다. 벨만-포드 알고리즘 - 매 단계마다 모든 edge(간선)을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge가 있어도 최적의 해를 찾을 수 있다. - 시간 복잡도가 느리다. 즉, 모든 edge의 가중치가 양수일 때는 다익스트라 알고리즘을, 음의 가중치를 갖는..