목록벨만포드 (1)
이숭간 공부기록
[알고리즘] 벨만-포드 알고리즘
벨만포드 알고리즘 최단경로라는것은 같은정점을 두번 지날일이 없기때문에 최단 경로의 간선개수는 최대 V-1개이다. 따라서 루프를 V-1번 (V는 노드의수) 돌리는데(최악의 경우까지 모두 커버가 가능), k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어 ( 이렇기 때문에 음의순환을 찾을때 한번더 수행하는것 ) 음수간선이 포함된 상황에서 최단거리 찾기 모든간선이 양수일때는 다익스트라를 사용하면 된다. 음수 간선의 순환이 발생하는 경우, 최단거리가 음의 무한인 노드가 발생한다. (계속해서 줄일수있으니까 무한대로 순환) 간선에 관하여 최단 경로문제는 다음과 같이 분류된다. 모든 간선이 양수인 경우 ( 다익스트라, 플로이드 와샬) 음수 간..
알고리즘/알고리즘 기초공부
2021. 8. 11. 23:22