Dot Algo∙ DS/알고리즘 개념
2021. 4. 25.
[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)
최단경로 알고리즘 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 위의 분류를 3가지 알고리즘을 통해 구할 수 있다. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수 벨만포드 알고리즘 벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 동작 과정 출발 노드를 설정한다. (to, ..
![[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/6w8RM/btq4Bwg2D3a/pkDFsWy8WqpLk56FDjHlC0/img.jpg)