welcome!

문제 보기https://www.acmicpc.net/problem/11657 벨만포드 알고리즘이다. 알고리즘 분류 기능을 이용해 풀수있는 가장 첫 문제이며, 벨만포드 알고리즘을 그대로 사용하면 된다.기존소스에 반례가 있었다. 출발점에서 도달 할 수 없는 정점 간에 음수 경로가 존재해도 음수사이클 존재를 판단했던 것이다. 그리고 INF 값이 너무 작았다. 500*10,000+1 이상되어야한다. 수정하였음. 등록일이 18년 2월이었으니... 1년 8개월만에 수정한거네요!` 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/11657.cc

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..

최단경로 문제와 벨만포드 알고리즘Shortest path Problem && Bellman-ford Algorithm (Label Correcting Algorithm)벨만의 1958년 연구 논문의 서론 부분이다. (RAND corp.) 두 번째 문단에서, " dynamic programming의 (함수 방정식 기법) 사용과 N-1번의 반복후에 수렴하는 반복적 알고리즘이 " 를 보자. 이게 바로 벨만-포드 알고리즘의 큰 핵심이다. Introduction 최단경로를 찾는 문제는 크게 두 종류로 나뉜다. 1 한 점에서 임의의 한 점(다른 모든 점) 까지의 최단경로를 찾는 문제2 모든 점 간의 최단경로를 찾는 문제 이 포스팅은 1번인 한 점에서 임의의 한 점 까지의 최단경로를 찾는 방법(알고리즘)에 대해서 포..