최단 경로1

• 

  [c++] 다익스트라 알고리즘 (백준-최단경로 1753) 다익스트라 알고리즘이란? 다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다. 다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다. 만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.) 다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다. /* 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무.. c++/알고리즘 2023. 1. 25.