반응형 116571 파이썬 (Python) - 벨만-포드(Bellman-Ford) 개념과 예제 (백준 11657) 벨만 포드 알고리즘 많이 알려져있는 다익스트라가 (시간 복잡도 O(ElogV)) 최단거리 구하는 알고리즘이라면, 벨만-포드 알고리즘(시간 복잡도 O(VE))은 다익스트라 보단 조금 느리지만, 음수엣지가 있어도 수행할수 있는 알고리즘입니다. 음수 엣지가 있는 그래프 탐색에선 '음수 사이클'이 생기는데, 그 음수 사이클을 판별하는 용도로도 쓸수 있습니다. 음수 사이클 같은 경우는 위 그래프의 2,4,5 노드의 사이클이라고 보시면 됩니다. 한 바퀴 돌때마다 -1씩 감소하므로, 최단거리가 음의 무한대로 발산할 수 있기 때문에 이 경우는 최단거리가 없는 경우입니다. 음의 엣지가 있는 그래프에서는 최단 거리를 구할 땐 음수 사이클이 없는지 확인하고 출력해야합니다 1. 등록된 모든 엣지를 가지고 엣지리스트와 각 노드.. 2022. 12. 31. 이전 1 다음
