[알고리즘] 다익스트라, 벨만포드 알고리즘(Dijkstra & Bellman-ford)

📕다익스트라 알고리즘 다익스트라 알고리즘은 가장 빠른 길을 찾을 때 주로 사용하는 알고리즘이다. 빠른 길을 찾을때 사용한다고? 그럼 BFS쓰면 되는거 아닌가? 라고 생각할 수 있다. 맞다 BFS를 사용하면 되지만 BFS를 사용하지 못하는 경우가 존재하는데 바로 비용이 존재할때이다. BFS의 경우 모든 간선의 비용이 동일해야하지만, 다익스트라는 모든 간선의 비용의 동일하지 않아도 사용가능하다. 다익스트라 알고리즘은 min_heap 우선순위큐를 사용하고, 간선을 키값으로 사용한다. 다익스트라 알고리즘에서 핵심은 e = w-> x 이다. 즉,dist[x] 1->2->3이 될 것이다. 하지만 다익스트라 알고리즘은 음수를 처리하지 못하기 때문에 각각의 간선에 음수비용의 양수값인 9를 더해준다. 그렇면 모두 9씩 ..

2021.06.18