> 벨만포드 알고리즘 다익 스트라 : 모든 간선의 비용이 양수일 때 최단 경로를 구할 수 있다. 심지어 음수간선이 포함되어 있더라도 해당 간선이 순환되는 구간이 없으면 된다. https://youtu.be/Ppimbaxm8d8 그러나 음수 간선이 순환되는 경우에는 다익스트라는 사용할 수 없고, 벨만 포드 알고리즘을 사용해야한다. 1. 출발 도시 설정 2. 최단 거리 테이블 무한으로 초기화 3. 벨만 포드 알고리즘 시행 3.1. 다음 과정을 n-1번 반복한다. 3.2. 만약 dist[a]의 값이 무한이 아니고, dist[b]의 값이 dist[a]+c값보다 크면? dist[b]에 dist[a]+c, 최단경로를 넣어준다. 3.3 만약 현재 i가 n인데도 갱신이 이뤄졌다면? -> 음수..