음의 가중치가 있는 최단거리알고리즘
start, destination, weight 로 구성됨
https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
벨만-포드 알고리즘 · ratsgo's blog
이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 벨만-포드 알고리즘(Bellman-Ford’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다. concept 최단경로 문제의 optimal substructure를 확장하면 최단경로를 다음과 같이 분해(decompostion)할 수 있습니다.
ratsgo.github.io
관련 문제
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
문제풀이
https://github.com/huisoo/algo_test/blob/master/timemachine_bak11657.java
huisoo/algo_test
Contribute to huisoo/algo_test development by creating an account on GitHub.
github.com
'알고리즘' 카테고리의 다른 글
| MST, 최소 신장 트리, 크루스칼 알고리즘 (0) | 2019.10.06 |
|---|
댓글