728x90
반응형
이론
이번에 볼 알고리즘은 벨만-포드 알고리즘이다. 최단 거리를 알고리즘 구하는 알고리즘 중 하나이다. 일반적인 다익스트라 알고리즘이나 플루이드-워셜 알고리즘이랑 다른점은 가중치가 음수인 점이다. 가중치가 음수라는 점에서 다익스트라 처럼 몇개의 간선만 선택 할 수 있는 점과 다르게 벨만-포드는 모든 간선을 봐야 된다는 점이다. 일단 벨만-포드 알고리즘을 알기위해서는 그래프에 대한 개념이 있어야 되기 때문에 그래프를 먼저 보고 공부하는 것을 추천한다.
[알고리즘 이론] 그래프(Grape)
이론 이번에 볼 자료구조는 그래프이다. 트리는 노드간에 부모-자식, 형제 이런 개념이 있지만 그래프는 노드하나 이상이 사이클을 가진 개념이다. 사이클이란 간선 한번만 이동 가능할때 노드
jih3508.tistory.com
그래프에 대한 개념이 잡혀있으면 벨만-포드 알고리즘을 공부하면된다. 자세한 설명은 아래의 영상을 보면된다.
https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13
728x90
반응형
'알고리즘 > 이론' 카테고리의 다른 글
| [알고리즘 이론] 투 포인터(Two Pointers) (0) | 2024.10.02 |
|---|---|
| [알고리즘 이론] LCS(Longest Increasing Subsequence) 최장 증가 부분 수열 (2) | 2024.02.06 |
| [알고리즘 이론] 스택(Stack) (0) | 2022.12.29 |
| [알고리즘 이론] 최단경로 알고리즘(다익스트라) (0) | 2022.12.23 |
| [알고리즘 이론] 그래프(Grape) (0) | 2022.12.23 |
