이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다. 저번 시간에 다익스트라 알고리즘에 대해 배웠는데다익스트라 알고리즘의 가장 중요한 특징 중 하나는edge의 weight들 중에 negative weight가 있으면 안된다는 점이다 기본적으로 다익스트라는 greedy algorithm에기초하고 있기 때문에negative weight가 있으면 기존에 확정 되었던 값이이후에 더 짧아지는 경우가 생길 수가 있는데이는 greedy algorithm의 기본적인 가정에 반하게 되는 것이기 때문이다 따라서 edge들의 weight에 음수가 있는 경우다익스트라 대신에 사용할 수 있는 알고리즘은 바로Bellman-Ford Algorithm이다 Bel..
